Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

YB_KT2B2 - Phần thưởng

TIMBERSAW oai hùng ngày nào nay đã trở thành bác bảo vệ của rừng Radiant (có dạng hình chữ nhật kích thước MxN). Để đền đáp công lao to lớn của TIMBERSAW, Chúa đất cho phép anh chọn một khu rừng hình chữ nhật có kích thước k*k, có các cạnh song song với các bìa rừng và Chúa đất chỉ cho phép anh khai thác cây trên đường biên của khu rừng đó. Biết giá trị của mỗi cây trong khu rừng Radiant là a[i,j] nguyên.

Bạn hãy giúp TIMBERSAW chọn một khu rừng có giá trị cao nhất mà vẫn thỏa mãn yêu cầu của Chúa đất.

Input

  • Dòng 1: Gồm 3 số m, n , k ( 0< k ≤ min(m,n); m,n ≤ 1000).
  • m dòng sau, mỗi dòng n số nguyên là giá trị của mỗi cây trong khu rừng.

Output

  • Một số duy nhất là giá trị cao nhất mà TIMBERSAW có thể nhận được.

Example

Input:
4 4 3
3 4 5 -5
-7 0 7 2
3 -7 6 -4
1 -6 -3 -5
Output:
14

Được gửi lên bởi:Vương Trung Hiếu Nghĩa
Ngày:2014-08-13
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CSHARP C++ 4.3.2 CPP JAVA PAS-GPC PAS-FPC
Nguồn bài:HSG cấp trường chuyên YÊN BÁI

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.