레이팅 미적용Alice and Bob decide to share a chocolate bar, which is an \(n\) by \(m\) rectangular grid of chocolate cells. They decide that Alice should get \(a < n \cdot m\) pieces and that Bob should get $b = n \cdot m -
a$ pieces. To split the chocolate bar, they repeatedly take a single piece of chocolate and break it either horizontally or vertically, creating two smaller pieces of chocolate. See Figure for an example.
What is the minimum number of splits that Alice and Bob need to perform in order to split the \(n\)-by-\(m\) chocolate bar into two piles consisting of \(a\) and \(b\) chocolate cells?
The input consists of a single line, containing the three integers \(n\), \(m\) and \(a\) (\(1 \le n, m \le 10^6\), \(1 \le a < n \cdot m\)).
Output the minimum number of splits needed to achieve the desired division of chocolate.
3 10 9
1
10 10 71
3