Donghyuk, King of the Board Game

Donghyuk found a very interesting-looking board game in a warehouse. The board consists of R x C square cells. 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.

The cells of this board are colored in an unusual way. Each cell is either gray or white.

Write the row number and the column number in binary. If there is at least one bit position where both numbers have a 1, the cell is white. For example, cell (4, 5) is white. Otherwise, the cell is gray. For example, cell (2, 5) is gray.

A 10 x 10 board looks like this:

Donghyuk's piece starts at (0, 0) and visits cells in the zigzag order shown in the picture: cells are grouped by increasing row+column value, odd-numbered diagonals are visited from top to bottom, and even-numbered diagonals are visited from bottom to top.

He wants to know how many times the piece visits a gray cell. Because the piece gets tired, it stops immediately after visiting K cells.

Given R, C, and K, compute how many gray cells the piece visits.

The first line contains R and C. (1 <= R, C <= 1,000,000)

The second line contains K. (1 <= K <= R x C)

Print the number of gray cells visited by Donghyuk's piece.