Mô tả và yêu cầu

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.
Input Output
3 6 2 13
1 2 1 3 1 1
2 1 4 1 4 3
1 2 1 4 1 1