보드 게임의 왕 김동혁

동혁이는 창고에서 매우 재미있어 보이는 보드 게임을 발견했다. 이 게임의 보드는 R x C개의 정사각형 칸으로 이루어져 있다. 행은 위에서부터 0부터 R-1까지, 열은 왼쪽에서부터 0부터 C-1까지 번호가 매겨져 있다.

각 칸은 회색 또는 흰색으로 칠해져 있다.

어떤 칸의 행 번호와 열 번호를 이진수로 나타냈을 때, 두 번호가 같은 위치에서 모두 1인 비트가 하나라도 있으면 그 칸은 흰색이다. 예를 들어 (4, 5)는 흰색이다. 그런 비트가 하나도 없으면 그 칸은 회색이다. 예를 들어 (2, 5)는 회색이다.

10 x 10 크기의 보드는 다음과 같이 생겼다.

동혁이의 말은 (0, 0)에서 시작해 그림에 표시된 지그재그 순서로 칸을 방문한다. 즉, row+column 값이 작은 대각선부터 차례로 방문하고, 홀수 번째 대각선은 위에서 아래로, 짝수 번째 대각선은 아래에서 위로 방문한다.

동혁이는 말이 방문한 칸 중 회색 칸의 수를 알고 싶다. 말은 K개의 칸을 방문하면 피곤해서 더 이상 방문하지 않는다.

R, C, K가 주어졌을 때, 말이 방문한 회색 칸의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 R과 C가 주어진다. (1 <= R, C <= 1,000,000)

둘째 줄에 K가 주어진다. (1 <= K <= R x C)

동혁이의 말이 방문한 회색 칸의 수를 출력한다.