An là một lập trình viên điện toán đám mây. Hiện tại, anh ấy đang cần phải chạy tổng cộng ~n~ chương trình mô phỏng trên "đám mây". Mỗi chương trình chạy mất đúng ~1~ đơn vị thời gian, nhưng bộ nhớ chúng sử dụng có thể khác nhau. Bộ nhớ cần thiết cho chương trình ~i~ là ~a_i~ megabyte.

Theo công việc, An phải chia ~n~ chương trình thành ~k~ tác vụ và số chương trình trong mỗi tác vụ không nhất thiết bằng nhau. Trong mỗi tác vụ, các chương trình được chạy lần lượt, tức là thời gian thực hiện một tác vụ sẽ bằng số chương trình trong tác vụ đó. Mặt khác, bộ nhớ được cấp cho mỗi tác vụ bằng bộ nhớ tối đa cần thiết cho bất kỳ một chương trình nào trong tác vụ đó.

Tuy nhiên, An phải trả chi phí cho mỗi megabyte trên một đơn vị thời gian, vì vậy chi phí cho mỗi tác vụ bằng số đơn vị thời gian thực hiện tác vụ đó nhân với bộ nhớ tối đa của các chương trình trong tác vụ đó.

Bạn hãy giúp An chia ~n~ chương trình thành ~k~ tác vụ, sao cho chi phí thực hiện chúng là tối thiểu.

Input

• Dòng đầu chứa hai số nguyên ~n~ và ~k~ (~1 \le k \le n \le 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~0 \le a_i \le 10^{12}~).

Output

• Ghi ra một số nguyên là chi phí tối thiểu mà An phải trả.

Sample Input 1

10 4
4 1 12 17 7 3 6 8 10 16

Sample Output 1

94

Giải thích ví dụ

Trong ví dụ trên, An cần chia thành ~4~ tác vụ như sau:

• Tác vụ 1: Gồm các chương trình thứ nhất, thứ hai và thứ sáu. Chi phí của tác vụ 1 là: ~3 \times \max(a_1, a_2, a_6) = 12~;
• Tác vụ 2: Gồm các chương trình thứ ba và thứ chín. Chi phí của tác vụ 2 là: ~2 \times \max(a_3, a_9) = 24~;
• Tác vụ 3: Gồm các chương trình thứ năm, thứ bảy và thứ tám. Chi phí của tác vụ 3 là: ~3 \times \max(a_5, a_7, a_8) = 24~;
• Tác vụ 4: Gồm các chương trình thứ tư và thứ mười. Chi phí của tác vụ 4 là: ~2 \times \max(a_4, a_{10}) = 34~. Tổng chi phí An cần phải trả là: ~12 + 24 + 24 + 34 = 94~.

Subtasks