Trò chơi đập bóng

Mô tả bài toán

Tuấn rất thích chơi game Line98 huyền thoại. Trong trò chơi này, nếu có 4 quả bóng cùng màu nằm liên tiếp theo chiều ngang, chiều dọc, hoặc đường chéo thì chúng sẽ nổ. Tuấn muốn phát triển một phiên bản mới của trò chơi này.

Một hình chữ nhật kích thước ~m \times n~ được chia thành các ô vuông, mỗi ô chứa một quả bóng được biểu diễn bằng số nguyên. Người chơi sẽ được cung cấp một chiếc búa và có thể dùng chiếc búa này để đập vỡ quả bóng bất kỳ. Khi một quả bóng bị đập, tất cả các quả bóng khác có cùng giá trị nằm trên cùng hàng, cột, hoặc đường chéo sẽ bị phá hủy. Mỗi lần đập bóng sẽ tốn một lượt, và người chơi chỉ có tối đa ~K~ lượt đập.

Ví dụ, với các quả bóng như ở ví dụ: M= 3, N=6, k=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ó 11 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: Nhiệm vụ của bạn là tìm cách đập bóng để phá hủy được nhiều quả bóng nhất trong ~K~ lượt đập.

Input

Dữ liệu được đọc từ tệp GAME.INP bao gồm:

Dòng đầu tiên chứa ba số nguyên ~m~, ~n~, ~k~: số hàng, số cột của bảng, và số lượt đập tối đa.
- ~1 \leq m, n \leq 300~, ~1 \leq k \leq m \times n~.
~m~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên ~a[i][j]~: giá trị trên các quả bóng trong bảng.
- ~1 \leq a[i][j] < 10,000~.

Output

Ghi ra tệp GAME.OUT một số nguyên: số lượng bóng tối đa có thể phá hủy.

Giới hạn

Subtask 1 (60% số điểm): ~m, n \leq 100~, ~a[i][j] \leq 300~.
Subtask 2 (40% số điểm): ~m, n \leq 300~, ~a[i][j] < 10,000~.

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:

Giải thích:

Đập vào bóng có giá trị 1: phá được 10 bóng.
Đập vào bóng có giá trị 4: phá thêm 3 bóng.
Tổng cộng phá được 13 bóng.