Cho ~N~ quả trứng được đưa vào dây chuyền theo thứ tự (quả trứng thứ ~i~ có thể tích là ~a_i~). Ở cuối dây chuyền đã có sẵn M thùng chứa trứng. Các thùng này nhận trứng theo quy tắc: chứa trứng cho đến khi đầy thì chuyển sang thùng khác. Hãy tính sức chứa ~K~ tối thiểu của mỗi thùng để M thùng này có thể chứa hết trứng theo quy trình trên.

Dữ liệu:

• Dòng đầu: Ghi 2 số nguyên ~n, m (0 <n, m ≤ 10^9)~</li>
• Các dòng tiếp theo: dãy ~a_i (0 <a_i ≤ 10^6)~.</li>

Kết quả:

• Một số duy nhất là số ~k~ tìm được.

Ví dụ:

INPUT

5  3
6
5
4
8
9

OUTPUT

12

GIẢI THÍCH:

• Thùng 1: ~a_1, a_2~
• Thùng 2: ~a_3, a_4~
• Thùng 3: ~a_5~