#216902. [CCO 2026] Asymmetry

Alice and Bob will play a game with a grid with rows and columns where is even. There is also a positive integer . Initially, each cell of the grid contains a value between and , inclusive, and each cell is unmarked. The players take turns alternately, with Alice going first. The game ends when the current player cannot make a move.

On each player's turn, they select an unmarked cell of the grid and an integer between and , inclusive. Then, they set the value of that cell to and mark all cells in the same column as the one selected (including the selected cell).

The asymmetry of the grid is the sum of the absolute differences between the value of one cell and its corresponding cell when horizontally reflected across the middle of the grid over all such pairs of cells. More formally, it is

where is the value of the cell in the -th row from the top and -th column from the left. For example, the following grid has an asymmetry of .

Alice wishes to minimize the asymmetry of the grid when the game ends while Bob wishes to maximize it. If both players play optimally, what is the asymmetry of the final grid?

The first line of input will consist of space-separated integers , , and (, is even, ).

The next lines each contain integers, where the -th line contains integers (), the values of the cells from left to right in the -th row from the top.

Output a single integer, the asymmetry of the final grid if Alice and Bob play optimally.

样例输入 1

3 2 1
1 0
1 0
0 0

样例输出 1

2

样例输入 2

1 10 21
4 2 0 6 7 6 9 9 10 21

样例输出 2

55

样例输入 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

Explanation of Output for Sample Input

There are only columns, so each player will make move. With Alice going first, she can perform the following moves:

• Select one of the cells with a value of in the first column and set its value to . Then the optimal move for Bob is to set the value of the cell on the same row in the second column to . The final grid will be like the original grid with exactly one of the first rows of s and s swapped. Such a grid has an asymmetry of .
• Select one of the cells in the second column and first rows and set its value to . Then the optimal move for Bob is to set the value of the cell on the same row in the first column to . Again, the final grid will be like the original grid with exactly one of the first rows of s and s swapped. Such a grid has an asymmetry of .
• Select one of the cells in the third row and set its value to . Then the optimal move for Bob can be to set the value of the other cell in the third row to . Note that the cell selected already had the value of , and that such a move is allowed. Then, the final grid will have a and a in each row, resulting in an asymmetry of .
• Select any cell and set its value to its current value. Then the optimal move for Bob is to set the value of the cell in the remaining unmarked column and third row to . The final grid will have a and a in each row, resulting in an asymmetry of .

We see that regardless of how Alice makes her move, Bob will be able to play in such a way that the asymmetry is at least . If Alice selects her first move optimally, she can ensure that Bob cannot make the final asymmetry more than . Thus, the asymmetry if both players play optimally is .

Explanation of Output for Sample Input

There is only a single row, so for each move, the current player will select an unmarked cell and set it to any value between and , inclusive. The game ends after each player has made moves, resulting in all cells being marked.

Explanation of Output for Sample Input

Note that the answer may not fit within a -bit integer.

The following table shows how the available marks are distributed: