Nagu is about to watch "Logan". PVR Allahabad has a special "Choose Your Auditorium" offer. The offer's conditions are as follows:

1. It is up to a costumer to choose an Auditorium to watch movie in;
2. If the chosen Auditorium has x (x > 0) empty seats at the given moment, then the ticket for such an Audi costs x Rupees.

The only ticket office of the PVR has a queue of n movie enthusiasts in front of it. Nagu has not stood in the queue yet, but he is already wondering what is the maximum and the minimum Rupees the PVR administration can earn if all n people buy tickets according to the conditions of this offer?

The costumer buy tickets in turn, the first person in the queue goes first, then goes the second one, and so on up to n-th person.

Input:

The first line contains two integers n and m (1 ≤ n, m ≤ 1000) — the number of costumers in the queue and the number of Auditorium at the PVR, correspondingly. The next line contains m integers a1, a2, ..., am (1 ≤ ai ≤ 1000) — ai stands for the number of empty seats in the i-th Audi before the ticket office starts selling tickets.

The numbers in the lines are separated by a space. It is guaranteed that there are at least n empty seats in total.

Output:

Print two integers — the maximum and the minimum money that the PVR administration can earn, correspondingly.