Giải bài trực tuyến

Cho dãy số nguyên a₁, a₂, …, 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 <= n₁ < n₂ < n₃ < ... < n_k = n

Đoạn thứ i là dãy con a_ni-1+1, a_ni-1+2, ..., a_ni, i=1, 2, ..k. Ở đây quy ước n₀=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≤ k ≤ n ≤ 15000).

Dòng thứ i trong số n dòng tiếp theo chứa số nguyên a_i (|a_i| ≤ 30000), i =1, 2, …, 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.

Example

Input:
9 4
1
1
1
3
2
2
1
3
1
Output:
5