레이팅 미적용Luka는 다락방에서 아주 특이한 게임판을 발견했다. 놀랍게도 이 판은 \(R \cdot C\)개의 정사각형 칸으로 이루어져 있다. 행에는 위에서 아래로 \(0\)부터 \(R-1\)까지, 열에는 왼쪽에서 오른쪽으로 \(0\)부터 \(C-1\)까지 번호가 붙어 있다.
이 판이 특이한 점은 칸에 색이 칠해진 방식이다. 각 칸은 회색이거나 흰색이다:
- 흰색: 칸의 행 번호와 열 번호를 이진법으로 나타냈을 때 같은 자리에 숫자 \(1\)이 적어도 하나 있는 경우. 예를 들어 칸 \((4, 5)\)는 흰색이다.
- 회색: 그 밖의 경우. 예를 들어 칸 \((2, 5)\)는 회색이다.
Luka의 고슴도치는 이 특이한 판 위를 걷는 것을 좋아한다. 고슴도치는 칸 \((0, 0)\)에서 걷기 시작해 지그재그(우경) 방식으로 나아간다: 행 \(0\)을 왼쪽에서 오른쪽으로 걷고, 행 \(1\)로 내려가 오른쪽에서 왼쪽으로 걷고, 다시 행 \(2\)를 왼쪽에서 오른쪽으로 걷는 식이다. 고슴도치가 걷는 동안 Luka는 고슴도치가 방문한 회색 칸의 수를 센다.
칸을 \(K\)개 방문하면 고슴도치는 지쳐서 잠들어 버린다.
판의 크기와 수 \(K\)를 미리 알고 있을 때, 결과를 계산하는 프로그램을 작성하시오.
첫째 줄에 판의 크기인 두 정수 \(R\) (\(1 \le R \le 1\,000\,000\))와 \(C\) (\(1 \le C \le 1\,000\,000\))가 주어진다.
둘째 줄에 고슴도치가 방문하는 칸의 총 개수인 정수 \(K\) (\(1 \le K \le R \cdot C\))가 주어진다. 이 수는 32비트 정수에 들어가지 않을 수 있음에 유의하시오.
고슴도치가 방문하는 회색 칸의 수를 출력한다.
채점: 전체 점수의 \(50\%\)에 해당하는 테스트 케이스에서는 \(K\)가 \(1\,000\,000\)보다 작다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 50점 | \(K < 1\,000\,000\) |
Subtask 2 | 50점 | No additional constraints. |
10 10
653 5
11810 10
10051