#1069 · Thay thế tổng chi phí - REPLACESUM

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.