Trung 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, Trung 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 phát 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, Trung 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ụ và bằng số chương trình của tác vụ đó nhân với bộ nhớ tối đa của các chương trình trong tác vụ. Chi phí thực hiện ~n~ chương trình sẽ là tổng chi phí thực hiện ~k~ tác vụ. Bạn hãy giúp Trung chia tác vụ phù hợp sao cho chi phí thực hiện chúng là tối thiểu nhé.

Input: Dòng đầu tiên 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,...,a_n~ với ~0 \le a_i \le 10^{12}~.

Output: một số nguyên là chi phí tối thiểu mà Trung phải trả.

Sample input:

10 4

4 1 12 17 7 3 6 8 10 16

Sample output:

94

Trong ví dụ trên, Trung 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í Trung cần phải trả là: ~12+24+24+34=94.~