Mô tả và yêu cầu

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ử a1, ..., aN và một số nguyên dương K.
Yêu cầu:
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 p hầ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ữ liệu vào

• Dòng đầu tiên chứa số nguyên dương N là số lượng phần tử (1 ≤ N ≤ 2 105 ) và
số nguyên dương K (2 ≤ K ≤ N).
• Dòng tiếp theo chứa N số nguyên ai (0 ≤ ai ≤ 109 ).

Dữ liệu ra

• 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. Example:
INPUT OUTPUT

4 2 10
1 2 3 4 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.

Giới hạn và chấm điểm

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