Đào vàng

Bối cảnh

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.\)

Yêu cầu

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

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

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

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

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

Output

82

Giải thích ví dụ

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.

Thông tin học tập

• Buổi: B18
• Concepts: 2D prefix sums, query optimization
• Giới hạn kiến thức: B01-B18
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 30