Ở xưởng xí nghiệp Bedao, có ~k~ người thợ và có ~n~ tấm bảng cần tô được đặt cạnh nhau, tấm bảng thứ ~i~ tô tốn mất ~a_i~ đơn vị thời gian. Tại một thời điểm, mỗi người thợ chỉ được tô một tấm bảng.

Để hoàn thành công việc này trong thời gian nhanh nhất có thể, ~k~ người thợ đã thống nhất chia ~n~ tấm bảng thành ~k~ phần phân biệt, mỗi phần gồm một hoặc một số tấm bảng bất kì trong ~n~ tấm bảng.

Dưới vai trò là một chủ xưởng xí nghiệp, bạn cần phải chia ~n~ tấm bảng thành ~k~ phần sao cho thời gian hoàn thành công việc là sớm nhất.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~( 1 \leq k \leq n \leq 12 )~
• ~n~ dòng tiếp theo là các số ~a_i~ là thời gian để tô tấm bảng thứ ~i~ ( ~1 \leq a_i \leq 10^3~ )

Output

• Một số nguyên là thời gian sớm nhất để hoàn thành công việc yêu cầu

Sample Input

4 3
1 
5 
3 
5

Sample Output

5

Note

Ta có thể chia ~4~ tấm bảng thành ~3~ phần như sau: ~{[1,3],[5],[5]}~ và có thời gian hoàn thành công việc là ~5~, cũng là thời gian hoàn thành sớm nhất