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,..., a_N$ và một số nguyên dương $K$.

Trong một thao tác, bạn được thực hiện:

• Nếu trong mảng còn ít nhất $K$ phần tử, bạn phải chọn ra $K$ phần tử nhỏ nhất (hoặc chọn tất cả nếu số lượng phần tử trong mảng ít hơn $K$) rồi thay thế 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 đến khi nào trong 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òng đầu tiên chứa số nguyên dương $N$ là số lượng phần tử $(1 \leq N \leq 2 \times 10^5)$ và số nguyên dương $K (2 \leq K \leq N)$.
• Dòng tiếp theo chứa $N$ số nguyên $a_i (0 \leq a_i \leq 10^9)$.

• 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.

• 50% test có $N \leq 2000$.
• 50% test còn lại không ràng buộc gì thêm.

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.