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ử.

Yêu cầu: 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.

Input

• 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 ai (0 ≤ ai ≤ 10^9).

Output

• 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.

Sample Input

4 2
1 2 3 4

Sample Output

10
3

Ràng buộc

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