An là giáo viên chủ nhiệm lớp \(12\)A2. Đầu năm học, thầy Hùng (giáo viên Toán) đưa cho An một dãy gồm \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) và yêu cầu An chia dãy thành đúng \(K\) mảng con liên tiếp (mỗi phần tử thuộc đúng một mảng con). Cô Mai yêu cầu thầy An phải làm sao cho tổng lớn nhất trong số \(K\) mảng con là nhỏ nhất có thể. Hãy giúp An tìm tổng lớn nhất nhỏ nhất này.

Ví dụ: Với dãy \([1, 2, 3, 4, 5]\) và \(K = 3\). Một cách chia: \([1, 2, 3]\), \([4]\), \([5]\) → tổng các mảng con lần lượt là \(6, 4, 5\). Tổng lớn nhất là \(6\). Đây là cách chia tối ưu.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(K\) (\(1 \le K \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) (\(0 \le a_i \le 10^5\)). Tổng \(\sum a_i \le 10^9\).

Định dạng đầu ra

• In ra một số nguyên là tổng lớn nhất của \(K\) mảng con (nhỏ nhất có thể).

Ví dụ

Input:

5 3
1 2 3 4 5

Output:

6

Ràng buộc

• \(1 \le K \le N \le 10^5\).
• \(0 \le a_i \le 10^5\).
• \(\sum_{i=1}^{N} a_i \le 10^9\).