Cho dãy ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~.

Hãy chia dãy ~a~ thành ~k~ đoạn liên tục sao cho tổng giá trị lớn nhất của các phần tử của một trong các đoạn này nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, k \ (k \le n);~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n \ (1 \le a_i \le 10^9, \ 1 \le i \le n)~.

Output

In ra kết quả của bài toán.

Scoring

• Subtask 1 [50%]: ~n \le 1000;~
• Subtask 2 [50%]: ~n \le 10^5.~

Examples

Input

10 4
1 3 2 4 10 8 4 2 5 3

Output

12

Giải thích: Chia dãy thành ~4~ đoạn ~(1, 3, 2, 4), (10), (8, 4), (2, 5, 3)~.