Alice và Bob chơi một trò chơi trên lưới có $N$ hàng và $M$ cột, trong đó $M$ là số chẵn. Ngoài ra còn có một số nguyên dương $K$. Ban đầu, mỗi ô của lưới chứa một giá trị từ $0$ đến $K$ (bao gồm cả $0$ và $K$), và mỗi ô đều chưa được đánh dấu. Hai người chơi lần lượt thực hiện các nước đi, Alice đi trước. Trò chơi kết thúc khi người chơi đến lượt không thể thực hiện nước đi nào nữa.

Trong mỗi lượt, người chơi chọn một ô chưa được đánh dấu và một số nguyên $a$ từ $0$ đến $K$ (bao gồm cả $0$ và $K$). Sau đó, họ đặt giá trị của ô đó thành $a$ và đánh dấu tất cả các ô trong cùng cột với ô vừa chọn (bao gồm cả ô được chọn).

Độ bất đối xứng (asymmetry) của lưới là tổng các giá trị tuyệt đối của hiệu giữa giá trị của một ô và giá trị của ô tương ứng khi phản chiếu theo chiều ngang qua giữa lưới, tính trên tất cả các cặp ô như vậy. Công thức chính thức là:

$$\sum_{1 \le i \le N} \left( \sum_{1 \le j \le M/2} |g_{i,j} - g_{i,M-j+1}| \right)$$

trong đó $g_{i,j}$ là giá trị của ô ở hàng thứ $i$ từ trên xuống và cột thứ $j$ từ trái sang. Ví dụ, lưới $2 \times 4$ sau đây có độ bất đối xứng là $|8-0| + |4-2| + |6-6| + |7-9| = 12$.

Alice muốn tối thiểu hóa độ bất đối xứng của lưới khi trò chơi kết thúc, trong khi Bob muốn tối đa hóa nó. Nếu cả hai người chơi đều chơi tối ưu, độ bất đối xứng của lưới cuối cùng là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào gồm ba số nguyên cách nhau bởi dấu cách $N$, $M$ và $K$ ($1 \le N, M \le 2000$, $M$ là số chẵn, $1 \le K \le 10^9$).

$N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên, trong đó dòng thứ $i$ chứa các số nguyên $g_{i,1}, \dots, g_{i,M}$ ($0 \le g_{i,j} \le K$), là giá trị của các ô từ trái sang phải trong hàng thứ $i$ từ trên xuống.

Dữ liệu ra

In ra một số nguyên duy nhất là độ bất đối xứng của lưới cuối cùng nếu Alice và Bob chơi tối ưu.

Ví dụ

Dữ liệu vào 1

3 2 1
1 0
1 0
0 0

Dữ liệu ra 1

2

Ghi chú 1

Chỉ có 2 cột, vì vậy mỗi người chơi sẽ thực hiện 1 nước đi. Với Alice đi trước, cô ấy có thể thực hiện các nước đi sau:

• Chọn một trong các ô có giá trị 1 ở cột đầu tiên và đặt giá trị của nó thành 0. Sau đó, nước đi tối ưu cho Bob là đặt giá trị của ô cùng hàng ở cột thứ hai thành 1. Lưới cuối cùng sẽ giống như lưới ban đầu với đúng một trong hai hàng đầu tiên của các số 0 và 1 bị hoán đổi. Lưới như vậy có độ bất đối xứng là $|1-0| + |0-1| + |0-0| = 2$.
• Chọn một trong các ô ở cột thứ hai và hai hàng đầu tiên và đặt giá trị của nó thành 1. Sau đó, nước đi tối ưu cho Bob là đặt giá trị của ô cùng hàng ở cột đầu tiên thành 0. Một lần nữa, lưới cuối cùng sẽ giống như lưới ban đầu với đúng một trong hai hàng đầu tiên của các số 0 và 1 bị hoán đổi. Lưới như vậy có độ bất đối xứng là 2.
• Chọn một trong các ô ở hàng thứ ba và đặt giá trị của nó thành 1. Sau đó, nước đi tối ưu cho Bob có thể là đặt giá trị của ô còn lại trong hàng thứ ba thành 0. Lưu ý rằng ô được chọn đã có giá trị 0, và nước đi như vậy là hợp lệ. Khi đó, lưới cuối cùng sẽ có một số 0 và một số 1 trong mỗi hàng, dẫn đến độ bất đối xứng là 3.
• Chọn bất kỳ ô nào và đặt giá trị của nó thành giá trị hiện tại. Sau đó, nước đi tối ưu cho Bob là đặt giá trị của ô ở cột chưa được đánh dấu còn lại và hàng thứ ba thành 1. Lưới cuối cùng sẽ có một số 0 và một số 1 trong mỗi hàng, dẫn đến độ bất đối xứng là 3.

Chúng ta thấy rằng bất kể Alice thực hiện nước đi như thế nào, Bob sẽ có thể chơi theo cách mà độ bất đối xứng ít nhất là 2. Nếu Alice chọn nước đi đầu tiên của mình một cách tối ưu, cô ấy có thể đảm bảo rằng Bob không thể làm cho độ bất đối xứng cuối cùng lớn hơn 2. Do đó, độ bất đối xứng nếu cả hai người chơi đều chơi tối ưu là 2.

Dữ liệu vào 2

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

Dữ liệu ra 2

55

Ghi chú 2

Chỉ có một hàng duy nhất, vì vậy cho mỗi nước đi, người chơi hiện tại sẽ chọn một ô chưa được đánh dấu và đặt nó thành bất kỳ giá trị nào từ 0 đến 21. Trò chơi kết thúc sau khi mỗi người chơi đã thực hiện 5 nước đi, dẫn đến tất cả 10 ô đều được đánh dấu.

Dữ liệu vào 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

Dữ liệu ra 3

3972378656

Ghi chú 3

Lưu ý rằng câu trả lời có thể không nằm trong phạm vi số nguyên 32-bit.