Yêu cầu

Một hệ thống máy chủ cần sao lưu N tệp tin vào K chiếc USB. Các tệp tin được đánh số từ 1 đến N, tệp tin thứ i có dung lượng là A_i Megabyte. Hệ thống yêu cầu mỗi chiếc USB phải chứa các tệp tin có số thứ tự liên tiếp nhau.

Để tiết kiệm chi phí mua sắm, người quản trị muốn mua K chiếc USB có cùng một mức sức chứa (dung lượng tối đa) giống nhau.

Yêu cầu: Tính mức sức chứa nhỏ nhất của mỗi chiếc USB sao cho có thể sao lưu thành công toàn bộ N tệp tin.

Dữ liệu vào

Đọc từ tệp SAOLUU.INP gồm:
Dòng thứ nhất chứa hai số nguyên dương N và K (N >= K).
Dòng thứ hai chứa N số nguyên dương A_1, A_2, ..., A_N.

Dữ liệu ra

Ghi ra tệp SAOLUU.OUT một số nguyên duy nhất là sức chứa nhỏ nhất của USB cần mua.

Ràng buộc

Subtask 1: 20% số điểm có 2 <= N <= 10; 1 <= A_i <= 100; K = 2;
Subtask 2: 30% số điểm có 10 <= N <= 100; 1 <= A_i <= 1000; 3 <= K <= 10;
Subtask 3: 50% số điểm có 100 <= N <= 10^5; 1 <= A_i <= 10^9; 3 <= K <= 10^3.

Ví dụ

Input:

4 2
10 20 30 40

Output:

60

Giải thích: USB 1 chứa tệp 10, 20, 30 (tổng 60). USB 2 chứa tệp 40 (tổng 40). Mức sức chứa cần thiết tối thiểu cho các USB là 60.