Ngoài đam mê về lập trình, Tuấn Anh rất thích chơi game, nhất là game Line98 huyền thoại. Ở đó, có 4 quả bóng cùng màu sẽ nổ khi nó đứng cạnh nhau theo chiều dọc hoặc chiều ngang hoặc theo đường chéo theo một đường thẳng. Với khả năng lập trình của mình, Tuấn Anh muốn phát triển game này lên với cách chơi mới.

Cũng với hình chữ nhật kích thước ~𝑚×𝑛~ được chia thành lưới ô vuông. Ở mỗi ô có một quả bóng mà trên nó có ghi một số nguyên. Người chơi sẽ được cầm một chiếc búa, mỗi lần đập vào quả bóng nào thì quả bóng đó vỡ và tất cả các quả bóng khác có số nguyên bằng số nguyên ở quả bóng đầu tiên bị đập vào thì cũng vỡ theo. Mỗi ván chơi, một người chơi được đập búa tối đa ~𝑘~ lần. Tất nhiên, khi các quả bóng đã vỡ hết thì không phải đập búa nữa.

Ví dụ, với các quả bóng như hình bên. ~𝑚= 3,𝑛=6,𝑘=2~ thì người chơi có thể chơi như sau:

• Dùng búa đập vào quả 1 và quả 3 sẽ có 12 quả bóng vỡ.

• Dùng búa đập vào quả 1 và quả 4 sẽ có 13 quả bóng vỡ.

Yêu cầu: Hãy giúp Tuấn Anh tìm cách đập bóng không quá ~𝑘~ lần sao cho vỡ được nhiều bóng nhất.

Dữ liệu vào:

• Dòng 1: Ghi số nguyên dương ~𝑚,𝑛,𝑘~.(~𝑚 ≤ 300,𝑛 ≤ 300,𝑘 ≤ 𝑚×𝑛~)

• 𝑚 dòng tiếp theo, mỗi dòng ghi ~𝑛~ số nguyên dương ~𝑎_{𝑖𝑗}~ là số ghi trên quả bóng có tọa độ (~𝑖,𝑗~). ~𝑎_{𝑖𝑗} < 100000~.

Kết quả:

• Ghi một số nguyên cho biết số lượng bóng vỡ nhiều nhất tìm được.

Ví dụ

Input

3 6 2
1 2 1 3 1 1
2 1 4 1 4 3
1 2 1 4 1 1

Output

13