Cho dãy số \(a_1, a_2, \ldots, a_n\). Tìm cách chia dãy \(a\) thành \(s + 1\) đoạn liên tiếp sao cho tổng các số trong đoạn lớn nhất là nhỏ nhất.

Đoạn lớn nhất của một cách chia là đoạn có tổng lớn nhất trong các đoạn được chia.

Dữ liệu vào:

• Dòng đầu tiên chứa 2 số nguyên \(n, s\) (\(2 \leq n \leq 1000, 1 \leq s \leq 50, s < n\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(|a_i| \leq 10^6\)).

Dữ liệu ra:

• Một số nguyên duy nhất là tổng các số trong đoạn lớn nhất theo cách chia tìm được.

Input 1

5 2
8 2 1 5 6

Output 1

8

Giải thích test 1: Cách chia tối ưu là {8}, {2, 1, 5}, {6}

Input 2

10 3
1 2 3 4 5 6 7 8 9 10

Output 2

17

Ràng buộc:

• 30% số test có \(n \leq 20, 0 \leq a_i \leq 10^6\);
• 30% số test có \(20 < n \leq 1000, 0 \leq a_i \leq 10^6\);
• 40% số test còn lại có \(n \leq 1000, |a_i| \leq 10^6\).