Bờm là đội trưởng một đội sinh viên tham dự thi kì thi lập trình thuật toán BDN. Thông tin cuộc thi như sau:

• Đề thi có ~N~ bài đánh số ~1, 2, \dots, N~;
• Đội Bờm có ~M~ thành viên, các thành viên có trình độ đồng đều, mỗi bài cần được một thành viên giải quyết độc lập và liên tục cho đến khi hoàn thành, việc giải bài ~i~ cần thời gian ~t_i~ phút;
• Tiêu chí xếp hạng các đội là đội nào giải được nhiều bài hơn xếp trước, nếu hai đội giải được cùng số bài thì đội nào có tổng chỉ số phụ nhỏ hơn xếp trước, chỉ số phụ của mỗi bài là số nguyên thời điểm hoàn thành bài đó (tính theo phút), cuộc thi được bắt đầu từ thời điểm ~0~.

Các cách phân công làm bài và thứ tự làm bài khác nhau sẽ cho tổng chỉ số phụ khác nhau. Chẳng hạn nếu ~N = 3, M = 2, t_1 = 5, t_2 = 10, t_3 = 15~, cách phân công ~{(1, 2), (3)}~ cho tổng chỉ số phụ ~35~, còn cách phân công ~{(2, 1), (3)}~ cho tổng chỉ số phụ ~40~. Để chiến thắng, Bờm muốn đội mình giải hết cả ~N~ bài với tổng chỉ số phụ nhỏ nhất có thể.

Yêu cầu: Tính tổng chỉ số phụ tối ưu để giải hết ~N~ bài.

Input

• Dòng 1: hai số nguyên ~N, M~ (~0 \le N \le 5 \times 10^4~; ~1 \le M \le 10^4~);
• Dòng 2: ~N~ số nguyên ~a_1, a_2, \dots, a_N~ (~0 \le a_i \le 30~).
• Dữ liệu kết thúc bằng dòng ghi hai số ~0 0~.

Output

• Kết quả mỗi test ghi trên một dòng số nguyên là tổng chỉ số phụ nhỏ nhất có thể đạt được.

Sample Input 1

3 2
5 10 15
2 3
23 30
0 0

Sample Output 1

35
53