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. 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ữ liệu
- 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).

Kết qủa
- 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.

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.

Ví dụ

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.