Cho số nguyên dương \(n\) và dãy \(a_1, a_2,..., a_n\)

Yêu cầu: Chia dãy trên thành \(k\) đoạn liên tiếp sao cho tổng các phần tử lớn nhất trong các đoạn này là nhỏ nhất.

Dữ liệu

• Dòng thứ nhất chứa số tự nhiên \(n\) và \(k (1 ≤k ≤n ≤10^5)\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n(1 ≤ a_i ≤ 10^9) \)

Kết quả

• In ra tổng phần tử lớn nhất trong các đoạn sau khi chia sao cho giá trị đó nhỏ nhất.

Sample Input

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

Sample Output

12

Giới hạn

- Subtask 1 (50% số test): n ≤1000
- Subtask 2 (50% số test): n ≤10^5