Trong một xưởng sản xuất bánh kẹo, các chiếc bánh sau khi làm xong sẽ lần lượt đi ra băng chuyền và được xếp vào các hộp có cùng dung lượng (không gian chứa) ~M~.

Cách xếp như sau:

• Khi bắt đầu ca làm việc, công nhân mở sẵn một hộp rỗng.
• Mỗi chiếc bánh sẽ được đặt vào hộp đang mở nếu hộp vẫn còn chỗ.
• Nếu hộp không còn đủ dung lượng, công nhân sẽ đóng hộp lại, rồi mở một hộp mới để tiếp tục xếp.

Trong một ca sản xuất có ~n~ chiếc bánh, được đánh số từ 1 đến ~n~ theo đúng thứ tự chúng ra khỏi dây chuyền.
Chiếc bánh thứ ~i~ chiếm không gian chứa là ~a_i~.

Ban giám đốc quy định rằng trong một ca, số lượng hộp sử dụng không được vượt quá ~k~.

Hãy tìm dung lượng nhỏ nhất ~M~ của hộp để có thể đóng gói hết ~n~ chiếc bánh mà số hộp dùng không vượt quá ~k~.

Input

Đọc từ tệp XEPBANH.INP:

• Dòng 1: hai số nguyên ~n~ và ~k~ (~1 \leq k \leq n \leq 15000~).
• Dòng 2: gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \leq a_i \leq 30000~).

Output

Ghi ra tệp XEPBANH.OUT một số nguyên duy nhất — dung lượng hộp ~M~ nhỏ nhất tìm được.

Sample

XEPBANH.INP

9 4
1 1 1 3 2 2 1 3 1

XEPBANH.OUT

5

Giới hạn

• 60% số test thỏa mãn: ~1 \leq k \leq n \leq 10^3~ và ~1 \leq a_i \leq 10^3~.
• 40% số test thỏa mãn: ~10^3 < k \leq n \leq 15000~ và ~10^3 < a_i \leq 30000~.