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_2,…,a_{n-1},a_n ~ và một số nguyên dương ~ k ~.

Trong một số 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ử.

Yêu cầu: Hãy cho biết phần tử còn lại 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*10^5 ) ~ và số nguyên dương ~ k ~ ~ (2≤k≤n) ~.
• Dòng tiếp theo chứa ~ n ~ số nguyên ~ a_1,a_2,…,a_n ~ ~ (0≤a_i≤10^9) ~.

Kết quả

• Dòng đầu tiên là phần tử còn lại trong mảng.
• Dòng thứ hai là tổng chi phí thực hiện.

Ràng buộc

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

Ví dụ:

Input 1

4 2
1 2 3 4 

Output 1

10
3