Thành phố xây dựng hệ thống nước sạch cần phải lắp ghép các đoạn ống có độ dài lần lượt là a1,a2, … an thành một đường ống thẳng, để lắp ghép cần một máy nâng nhưng khả năng của nó mỗi lúc chỉ nối được tối đa k đoạn ống và chi phí để nối chính là tổng độ dài của đoạn đó sau khi nối. Bạn hãy lập trình tính tổng chi phí nối là ít nhất

Input

Dòng thứ nhất chứa hai số nguyên dương n và k (1< k < n <=10^5)

Dòng tiếp theo chứa n số nguyên dương là độ dài của n đoạn ống cần nối có giá trị không vượt quá 3*10^4

Output

Một số nguyên dương duy nhất là tổng số chi phí ít nhất để nối hệ thống cấp nước

Ví dụ 1:

Input

3 2
8 4 6

Output

28

Giải thích: Mỗi bước chỉ nối tối đa được 2 đoạn, nếu ta nối 8 với 4 tốn chi phí là 8+4=12 sau khi nối xong còn 2 đoạn độ dài 12 và 6 nối lại với nhau tốn 12+6=18 tổng chi phí nối là 12+18=30. Nếu ta nối 4 với 6 trước tốn 10 và còn 2 đoạn 10 và 8 nối lại với nhau tốn 18 do đó tổng kinh phí ít hơn chỉ còn 28.

Ví dụ 2:

Input

6 3
8 2 1 5 2 3

Output

39

Giải thích:

Bước 1: lắp các đoạn 1+2+2 tốn 5 bây giờ sẽ giảm đi 1, 2, 2 và thêm vào đoạn 6 nên còn các đoạn 8,5,3,5

Bước 2: lắp các đoạn 5+3+5 tốn 13 bây giờ sẽ giảm đi 5, 3, 5 và thêm vào đoạn 13 nên còn các đoạn 8, 13

Bước 3: lắp nốt 8+13 tốn 21

Tổng chi phí 5+13+21 = 39