Lưới tổ ong

View as PDF

Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Cho một lưới tổ ong có hình dạng tam giác như hình vẽ dưới đây.

Lưới gồm n hàng, các hàng được đánh số từ 1 đến n từ trên xuống dưới. Hàng thứ ii số, các số được đánh số từ 1 đến i. Một lưới tổ ong hình dạng tam giác kích thước k là một lưới con gồm k.

Yêu cầu: Tính tổng giá trị lớn nhất trong tất cả lưới tổ ong hình dạng tam giác kích thước k.

Input

  • Dòng đầu chứa hai số nguyên n,k(1kn3000);
  • Tiếp theo là n dòng, dòng thứ i chứa i số nguyên mô tả lưới tổ ong hình tam giác. Các số nguyên không âm và không vượt quá 109.

Output

  • Gồm một dòng chứa một số là tổng cần tính.
Ví dụ:
input
Copy
4 2
3
1 2
4 2 1
6 1 4 2
output
Copy
23

Comments

Please read the guidelines before commenting.


There are no comments at the moment.