Hôm nay Nhật được thầy Hùng cho một bài tập như sau:

Cho một dãy số gồm ~N~ phần tử ~a_1, \ldots, a_N~ và một số nguyên dương ~K~. Trong một thao tác, bạn thực hiện:

• Chọn ra ~K~ phần tử nhỏ nhất của mảng (nếu mảng có ít hơn ~K~ phần tử thì chọn tất cả) rồi thay thế chúng bằng một phần tử có giá trị bằng tổng của chúng.

• Chi phí cho mỗi lần thực hiện chính là hiệu của số lớn nhất và số nhỏ nhất trong các số vừa chọn.

• Lặp lại thao tác cho đến khi mảng còn đúng một phần tử.

In ra phần tử cuối cùng xuất hiện trong mảng và tổng chi phí thực hiện.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~N~ là số lượng phần tử ~(1 \le N \le 2 \cdot 10^5)~ và số nguyên dương ~K~ ~(2 \le K \le N)~.

• Dòng tiếp theo chứa ~N~ số nguyên ~a_i~ ~(0 \le a_i \le 10^9)~.

Kết quả

• Dòng đầu tiên là phần tử cuối cùng xuất hiện trong mảng.

• Dòng tiếp theo là tổng chi phí thực hiện.

Ví dụ

Sample Input

4 2
1 2 3 4

Sample Output

10
3

Giải thích

Với ~K = 2~:

• 2 số nhỏ nhất là 1 và 2, số được thay thế là 3 và chi phí thay thế là 2 - 1 = 1.

Mảng hiện tại: [3, 3, 4].

• 2 số nhỏ nhất là 3 và 3, số được thay thế là 6 và chi phí thay thế là 3 - 3 = 0.

Mảng hiện tại: [6, 4].

• 2 số nhỏ nhất là 6 và 4, số được thay thế là 10 và chi phí thay thế là 6 - 4 = 2.

Mảng hiện tại: [10].

Vậy phần tử cuối cùng là 10 và chi phí là 1 + 0 + 2 = 3.

Chấm điểm

• 50% test có ~N \le 2000~.

• 50% test còn lại không ràng buộc gì thêm.