2023 : Jez
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)

Luka found a very unusual game board in his attic. Surprisingly, it consists of R·C square cells. The
rows are numbered 0 to R−1 top to bottom and the columns 0 to C−1 left to right.
What makes the board unusual is the way in which the cells are coloured. Each cell is either grey or
white:
· White, if the row and column numbers of the cell, when represented in binary, have at least one
digit 1 in the same position. For example, the cell (4, 5) would be white.
· Grey, otherwise. For example, the cell (2, 5) would be grey.
The following image shows a board of size 10·10.


Luka's hedgehog likes walking on this unusual board and does it in an unusual way. The hedgehog
starts his walk in the cell (0, 0) and continues in the zig-zag pattern as in the second image above. While
the hedgehog is walking, Luka counts how many grey squares it visited.
After visiting K squares, the hedgehog gets tired and falls asleep. Luka then goes to bed too, happy that
he was able count the grey squares.
Task
Knowing the dimensions of the board and the number K beforehand, however, it is possible to write a
program that calculates the result faster. This is your task.
Input
The first line contains two integers R (1 ≤ R ≤ 1 000 000) and C (1 ≤ C ≤ 1 000 000), the dimensions of
the board.
The second line contains the integer K (1 ≤ K ≤ R·C), the total number of squares the hedgehog visits.
Note that this number may not fit in a 32-bit integer.
Output
Output the number of grey cells the hedgehog visits.
Scoring
In test cases worth 50% of points, K will be less than 1 000 000.

Reference: COCI 2008/2009, Contest #1 – October 18, 2008

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
10 10 6	5
3 5 11	8
10 10 100	51

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้