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.

Input

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

Output

Kết quả: Một số duy nhất là số \(k\) tìm được.

Sample Input

5 3
6
5
4
8
9

Sample 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\)