Alice와 Bob은 $N$개의 행과 $M$개의 열로 이루어진 격자에서 게임을 합니다. 여기서 $M$은 짝수입니다. 또한 양의 정수 $K$가 주어집니다. 처음에 격자의 각 칸은 $0$ 이상 $K$ 이하의 값을 가지며, 모든 칸은 표시되어 있지 않습니다(unmarked). 두 플레이어는 번갈아 가며 수를 두며, Alice가 먼저 시작합니다. 현재 플레이어가 더 이상 움직일 수 없게 되면 게임이 종료됩니다.
각 플레이어의 차례가 되면, 그들은 격자의 표시되지 않은 칸 하나와 $0$ 이상 $K$ 이하의 정수 $a$를 선택합니다. 그런 다음, 선택한 칸의 값을 $a$로 설정하고 선택한 칸과 같은 열에 있는 모든 칸(선택한 칸 포함)을 표시합니다.
격자의 비대칭도(asymmetry)는 격자를 가로로 반으로 접었을 때 대응되는 두 칸의 값의 차이의 절댓값을 모든 대응되는 칸의 쌍에 대해 합한 값입니다. 더 형식적으로 정의하면 다음과 같습니다.
$$\sum_{1 \le i \le N} \left( \sum_{1 \le j \le M/2} |g_{i,j} - g_{i,M-j+1}| \right)$$
여기서 $g_{i,j}$는 위에서부터 $i$번째 행, 왼쪽에서부터 $j$번째 열에 있는 칸의 값입니다. 예를 들어, 다음 $2 \times 4$ 격자의 비대칭도는 $|8-0| + |4-2| + |6-6| + |7-9| = 12$입니다.
| 8 | 4 | 2 | 0 |
|---|---|---|---|
| 6 | 7 | 9 | 6 |
Alice는 게임이 끝났을 때 격자의 비대칭도를 최소화하려고 하고, Bob은 이를 최대화하려고 합니다. 두 플레이어가 최적으로 플레이한다면, 최종 격자의 비대칭도는 얼마입니까?
입력
첫 번째 줄에는 세 개의 정수 $N, M, K$가 공백으로 구분되어 주어집니다 ($1 \le N, M \le 2000$, $M$은 짝수, $1 \le K \le 10^9$).
다음 $N$개의 줄에는 각각 $M$개의 정수가 주어지며, $i$번째 줄은 위에서부터 $i$번째 행의 왼쪽부터 오른쪽까지의 칸 값 $g_{i,1}, \dots, g_{i,M}$을 나타냅니다 ($0 \le g_{i,j} \le K$).
출력
Alice와 Bob이 최적으로 플레이했을 때 최종 격자의 비대칭도를 정수로 출력하십시오.
서브태스크
| 배점 | $N$의 범위 | $M$의 범위 | $K$의 범위 |
|---|---|---|---|
| 2점 | $N = 1$ | $2 \le M \le 2000$ | $1 \le K \le 10^9$ |
| 3점 | $1 \le N \le 2000$ | $M = 2$ | $K = 1$ |
| 3점 | $1 \le N \le 2000$ | $M = 2$ | $1 \le K \le 10$ |
| 3점 | $1 \le N \le 2000$ | $M = 2$ | $1 \le K \le 10^9$ |
| 4점 | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $K = 1$ |
| 4점 | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $1 \le K \le 10$ |
| 6점 | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $1 \le K \le 10^9$ |
예제
입력 1
3 2 1 1 0 1 0 0 0
출력 1
2
참고 1
열이 2개뿐이므로 각 플레이어는 1번씩 움직입니다. Alice가 먼저 시작할 때 가능한 움직임은 다음과 같습니다.
- 첫 번째 열에서 값이 1인 칸 중 하나를 선택하여 0으로 바꿉니다. 그러면 Bob의 최적의 수는 같은 행의 두 번째 열에 있는 칸을 1로 바꾸는 것입니다. 최종 격자는 원래 격자에서 0과 1로 이루어진 첫 두 행 중 하나가 바뀐 형태가 됩니다. 이러한 격자의 비대칭도는 $|1-0| + |0-1| + |0-0| = 2$입니다.
- 두 번째 열의 첫 두 행 중 하나를 선택하여 1로 바꿉니다. 그러면 Bob의 최적의 수는 같은 행의 첫 번째 열에 있는 칸을 0으로 바꾸는 것입니다. 마찬가지로 비대칭도는 2가 됩니다.
- 세 번째 행의 칸 중 하나를 선택하여 1로 바꿉니다. 그러면 Bob의 최적의 수는 세 번째 행의 다른 칸을 0으로 바꾸는 것입니다. 선택된 칸은 이미 0이었으며, 이러한 움직임은 허용됩니다. 최종 격자는 각 행에 0과 1을 하나씩 가지게 되어 비대칭도는 3이 됩니다.
- 아무 칸이나 선택하여 현재 값으로 설정합니다. 그러면 Bob의 최적의 수는 남은 표시되지 않은 열의 세 번째 행 칸을 1로 바꾸는 것입니다. 최종 격자는 각 행에 0과 1을 하나씩 가지게 되어 비대칭도는 3이 됩니다.
Alice가 어떻게 움직이든 Bob은 비대칭도가 최소 2가 되도록 플레이할 수 있음을 알 수 있습니다. Alice가 첫 수를 최적으로 선택하면 Bob이 최종 비대칭도를 2보다 크게 만들 수 없도록 보장할 수 있습니다. 따라서 두 플레이어가 최적으로 플레이할 때의 비대칭도는 2입니다.
입력 2
1 10 21 4 2 0 6 7 6 9 9 10 21
출력 2
55
참고 2
행이 하나뿐이므로, 각 플레이어는 자신의 차례에 표시되지 않은 칸을 선택하여 0에서 21 사이의 값으로 설정합니다. 각 플레이어가 5번씩 움직여 총 10개의 칸이 모두 표시되면 게임이 종료됩니다.
입력 3
4 6 986754321 219759391 882760615 762656191 423465948 621463211 136889371 215621504 385106915 740086459 417915224 551800597 572994766 176308756 365311996 635683450 907755406 590000050 586083433 607011121 457147795 837558908 684766852 946836347 303039615
출력 3
3972378656
참고 3
정답이 32비트 정수 범위를 벗어날 수 있음에 유의하십시오.