#423. DPBONUS – Phần thưởng ý nghĩa

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Trong cuộc thi đường lên đỉnh Olympia do nhà trường tổ chức, bạn Vân đã giành được vòng nguyệt quế. Để khích lệ, cô giáo chủ nhiệm quyết định tặng bạn Vân những món quà ý nghĩa. Cô giáo chủ nhiệm có chuẩn bị rất nhiều món quà, mỗi mòn quà lại có giá trị nhất định. Cô ghi giá trị của tất cả các món quà của cô lên một bảng hình vuông kích thước n\times n , mỗi ô một số là giá trị của một món quà. Ô ở dòng i cột j được gọi là ô (i, j) . Cô giáo cho bạn Vân được chọn một hình vuông kích thước k\times k , bạn Vân sẽ nhận được tất cả các món quà có giá trị tương ứng trên hình vuông k\times k đó. Em hãy giúp bạn Vân tính xem tổng giá trị tối đa của các món quà bạn Vân có thể nhận được là bao nhiêu nhé.

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên dương n, k cách nhau bởi một dấu cách;
  • n dòng tiếp theo, dòng thứ i chứa n số nguyên dương là giá trị của các món quà cô ghi trên dòng thứ i .

Dữ liệu ra:

  • Một số nguyên duy nhất là tổng giá trị các phần quà lớn nhất mà bạn Vận có thể nhận được.

Ví dụ:

Dữ liệu vào:
4 3
1 9 1 1
9 9 9 9
1 9 9 9
1 9 9 14
Dữ liệu ra:
86
Giải thích:
  • Cách chọn hình vuông 3\times 3 có đỉnh trái trên là ô (2, 2) , đỉnh phải dưới là ô (4, 4) , tổng giá trị là 86 .

Giới hạn:

  • 1 ≤ k ≤ n ≤ 1000 , giá trị của các món quà không vượt quá 1000 .