Bác Ba là tài xế xe tải chuyên chở hàng cho Công ty Bưu điện. Hôm nay bác nhận \(M\) gói hàng xếp thành một hàng dọc, gói thứ \(i\) có trọng lượng \(w_i\) (kg). Theo quy định, bác phải giao các gói theo đúng thứ tự từ đầu đến cuối, mỗi ngày chỉ được lấy một số gói liên tiếp từ đầu hàng cho lên xe. Nếu một gói đã được lấy đi rồi thì không thể lấy lại hôm sau. Sếp yêu cầu bác Ba phải giao hết số hàng trong đúng \(D\) ngày. Bác Ba muốn tìm sức chở nhỏ nhất của xe (tính theo kg) để có thể hoàn thành công việc đúng hạn.

Ví dụ: Với \(M = 5\) gói hàng trọng lượng \([1, 2, 3, 1, 1]\) và \(D = 2\) ngày. Nếu sức chở là \(5\), ngày \(1\) chở được \([1, 2]\); ngày \(2\) chở \([3, 1, 1]\) (tổng \(5\)). Đủ! Vậy sức chở nhỏ nhất là \(5\).

Hãy giúp bác Ba tính sức chở cần thiết.

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

• Dòng đầu chứa hai số nguyên \(N\) và \(D\) (\(1 \le D \le N \le 5 \times 10^4\)).
• Dòng thứ hai chứa \(N\) số nguyên \(w_1, w_2, \ldots, w_N\) (\(1 \le w_i \le 500\)).

Định dạng đầu ra

• In ra một số nguyên duy nhất là sức chở tối thiểu của xe tải.

Ví dụ

Input:

5 2
1 2 3 1 1

Output:

5

Giải thích:

• Với sức chở \(5\): ngày \(1\) chở \([1, 2]\) (tổng \(3 \le 5\)), ngày \(2\) chở \([3, 1, 1]\) (tổng \(5 \le 5\)). Hoàn thành trong \(2\) ngày.
• Với sức chở \(4\): bất kỳ cách chia nào cũng cần hơn \(2\) ngày.

Ràng buộc

• \(1 \le D \le N \le 5 \times 10^4\)
• \(1 \le w_i \le 500\)
• Sức chở nhỏ nhất không vượt quá \(\sum_{i=1}^{N} w_i\)