Sister Cities High

On a coordinate line, there are N cities. The task is to select K different pairs of these cities and designate the cities in each pair as twin cities. Each city can have at most one twin city. Your goal is to determine the maximum and minimum possible total distances between the twin cities.

Constraints

N and K are integers where 1 ≤ N ≤ 100000 and 0 ≤ K ≤ N/2. The coordinates of the cities do not exceed 10^9 in absolute value.

Input

The first line contains the integers N and K. The second line contains N integers representing the coordinates of the cities.

Output

Output two numbers on a single line: the maximum and minimum total distances that can be achieved between the twin cities in K pairs.

Examples