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 a1, a2, ..., an(1 ≤ai ≤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