Cho dãy số nguyên ~a_{1}, a_{2}, \dots, a_{n}~ và số nguyên dương ~k~. Ta gọi ~k~-phân đoạn của dãy số đã cho là cách chia dãy số đã cho ra thành ~k~ đoạn, mỗi đoạn là một dãy con gồm các phần tử liên tiếp của dãy. Chính xác hơn, một ~k~-phân đoạn được xác định bởi dãy chỉ số

~1 \le n_{1} < n_{2} < n_{3} < \dots < n_{k} = n~

Đoạn thứ ~i~ là dãy con ~a_{n_{i-1} + 1}, a_{n_{i-1} + 2}, \dots, a_{n_i}, i = 1, 2, \dots, k~. Ở đây quy ước ~n_{0} = 0~

Yêu cầu: Hãy xác định số ~M~ nhỏ nhất để tồn tại ~k~-phân đoạn sao cho tổng các phần tử trong mỗi đoạn đều không vượt quá ~M~.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~(1 \leq k \leq n \leq 15\,000)~.

Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa số nguyên ~a_{i}~ (~|a_{i}| \leq 30\,000~), ~i = 1, 2, \dots, n~.

Các số cạnh nhau trên một dòng trong file dữ liệu cách nhau ít nhất một dấu cách.

Output

Gồm một số nguyên duy nhất là giá trị ~M~ tìm được.

Sample Input

9 4
1
1
1
3
2
2
1
3
1

Sample Output

5