Cho một dãy số gồm \(N\) phần tử \(a_1,a_2 ..., 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ử.

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 \(a_i (0 ≤ a_i ≤ 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.