Problem Description

There is a rectangle with a length of $r$ and a width of $c$, which is divided into $r \times c$ small rectangles of size $1 \times 1$.

Rows are numbered from 0 to $r-1$ from top to bottom, and columns are numbered from 0 to $c-1$ from left to right.

Each small rectangle has a color. If a small rectangle is in row $x$ and column $y$, then:
- If $x \oplus y = x + y$, this small rectangle is gray.
- Otherwise, it is white.

The left image below shows the case where $r = c = 10$:

Now, someone walks along the trajectory shown in the right image for $k$ steps. Calculate how many gray squares they have walked on.

Input Format

The first line contains two integers $r$ and $c$.

The second line contains an integer $k$.

Output Format

A single line indicating the number of gray squares walked on.

Sample Input and Output

Sample Input #1

10 10
6

Sample Output #1

5

Sample Input #2

3 5
11

Sample Output #2

8

Sample Input #3

10 10
100

Sample Output #3

51

Notes

Data Size and Constraints

• For $50\%$ of the data, $k \le 10^6$.
• For $100\%$ of the data, $1 \le r, c \le 10^6$, $1 \le k \le r \times c$, and the answer is within the range of a 32-bit integer.

Note:

This problem is translated from COCI2008-2009 CONTEST #1 JEZ, translated by @菜鸟一只.

见题面 Input 部分

见题面 Output 部分