Bài 4. Phân công công việc (PLAN)

Hôm nay chúng ta lại bắt đầu một ngày làm việc bận rộn của Mark — một CEO của tập đoàn Space X. Thử thách cho các bạn hôm nay đó là phân công công việc cho các nhân viên sao cho hiệu quả nhất. Thông tin cụ thể như sau, tập đoàn có \(n\) dự án cần hoàn thành, được đánh số từ \(1\) đến \(n\). Mỗi dự án có một giá trị là lợi nhuận thu được sau khi thực hiện dự án thứ \(i\), gọi là \(a_i\).

Hiện tại, tập đoàn phân bổ \(k\) nhân viên để thực hiện một số dự án. Để thuận tiện cho khâu quản lý, mỗi nhân viên chỉ có thể nhận một số dự án liên tiếp nhau, tức là một nhân viên có thể nhận một hoặc nhiều dự án liền kề, và mỗi dự án chỉ được giao cho một nhân viên. Một số dự án không có lợi nhuận hoặc thua lỗ có thể không được giao cho bất kỳ nhân viên nào.

Mục tiêu của tập đoàn là phân công các dự án cho các nhân viên sao cho tổng giá trị lợi nhuận các dự án mà nhân viên thực hiện là cao nhất có thể. Tổng giá trị công việc mà mỗi nhân viên thực hiện được tính bằng tổng giá trị các dự án mà người đó đảm nhiệm; nếu nhân viên không nhận dự án nào thì giá trị bằng 0.

Các bạn hãy tìm cách phân chia các dự án cho các nhân viên sao cho tổng lợi nhuận các dự án mà tất cả các nhân viên thực hiện là lớn nhất.

Input

Cho trong file PLAN.INP, có cấu trúc:

• Dòng 1: Chứa hai số nguyên dương lần lượt \(n,k\) \((1 \le n \le 2000)\).
• Dòng 2: Chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) \((|a_i| \le 10^9)\).

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Ghi ra file PLAN.OUT:

• Dòng 1: Ghi một số nguyên là tổng lợi nhuận lớn nhất.

Example

5 1
1 -2 3 -1 4

6

5 2
1 -2 3 -1 4

7

Scoring

• Có \(1/3\) số điểm tương ứng với \(1 \le n \le 80\).
• Có \(1/3\) số điểm tương ứng với \(81 \le n \le 300\).
• Có \(1/3\) số điểm tương ứng với \(301 \le n \le 2000\).