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.