#### Start

2019-11-06 11:00 AKST

## NCPC 2019 (yet again)

#### End

2019-11-06 16:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -274 days 19:00:20

5:00:00

0:00:00

# Problem CCocoa Coalition

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 1 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? Figure 1: Illustration of a solution to Sample Input 2, showing the original $10$-by-$10$ chocolate bar split three times into pieces of size $10$-by-$2$, $10$-by-$5$, $3$-by-$3$ and $7$-by-$3$. Giving Alice the $10$-by-$5$ and $7$-by-$3$ pieces, she gets a total of $50 + 21 = 71$ chocolate cells.

## Input

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

Output the minimum number of splits needed to achieve the desired division of chocolate.

Sample Input 1 Sample Output 1
3 10 9

1

Sample Input 2 Sample Output 2
10 10 71

3