buitrunghieu là một nhà khai khoáng đầy tham vọng. Ông sở hữu nhiều mảnh đất, mỗi mảnh đều chứa lượng vàng tiềm năng. Cụ thể, ông có \(n×m\) mảnh đất, mỗi mảnh có diện tích một đơn vị và chứa một số lượng vàng nhất định. Ông có một dụng cụ khai thác đặc biệt có khả năng khai thác vàng từ một khu vực hình vuông kích thước \(k×k.\)

Cho biết một ma trận số nguyên \(A\) kích thước \(n×m\) biểu diễn số lượng vàng trong mỗi mảnh đất, hãy tìm cách sử dụng dụng cụ khai thác để chọn ra khu vực hình vuông \(k×k\) sao cho tổng số lượng vàng thu được là lớn nhất có thể.

INPUT FORMAT

Dòng đầu tiên nhập vào ba số nguyên dương \(n, m, k(1 \leq k \leq n, m\leq 10^3)\).

\(N\) dòng tiếp theo mỗi dòng nhập \(n\) số nguyên là giá trị của \(a_{i,j} (|a_{i,j}| \leq 10^3)\).

OUTPUT FORMAT

In ra một số là tổng số lượng vàng thu được lớn nhất.

Ví dụ 1:

Input

5 5 3
1 1 9 9 9
1 1 9 9 9
1 1 9 9 9
1 1 9 9 10
1 1 9 9 9

Ouput

82

Giải thích ví dụ mẫu

Sắp xếp tất cả các phần tử trong ma trận theo thứ tự tăng dần và sau đó in ma trận đã sắp xếp.

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House