Cửa hàng Lotteria HP có một dây chuyền sản xuất bánh Pizza. Có N cái bánh được đưa vào dây chuyền theo thứ tự (cái bánh i có thể tích là Ai). Ở cuối dây chuyền đã có sẵn M thùng chứa bánh. Các thùng này nhận bánh theo quy tắc: chứa bánh cho đến khi đầy thì chuyển sang thùng khác. Trưởng bộ phận thiết kế HMP được giao nhiệm vụ thiết kế thùng chứa bánh. Bạn hãy giúp HMP tính sức chứa tối thiểu K của mỗi thùng để M thùng này có thể chứa hết số bánh theo quy trình trên.

Dữ liệu: - Dòng dầu: Ghi hai số nguyên N,M (0<N, M<=10^9), Các dòng tiếp theo: dãy Ai (0<Ai<=10^6).

Kết quả: Duy nhất một số nguyên là số K tìm được.

VD: 

5 3 

6

5

4

8

9

Output:

12

Giải thích:

Thùng 1: A1,A2; Thùng 2: A3,A4; Thùng 3: A5