Napoleon is known as one of the best military commanders in history. One of his greatest victories occurred at the Battle of Austerlitz where he dealt a decisive defeat to his enemy while using fewer troops. At the battle of Austerlitz, the troops on both sides are arranged into an equal number of columns, with a certain number of troops in each column. Each of Napoleon's troops are evenly matched with the enemy's. The columns then advance on each other and whichever column has more troops will break through to the other side. The victor is the side that achieves the most breakthroughs. Given the enemy arrangement and the number of troops available, determine Napoleon's optimal troop deployment to maximize breakthroughs. If there are multiple deployments that achieve the maximum number of breaks, the optimal deployment is the one that minimizes breaks achieved by the enemy by matching the number of troops in their column.

Input Specification

The first line of input contains ~n~ ~(0 \le n \le 10^6)~ representing the number of troops Napoleon can deploy.
The next line of input contains ~c~ ~(1 \le c \le 10^6)~ representing the number of troop columns in this battle.
The next line contains ~c~ space separated integers ~(0 \le c_i \le 10^6)~ representing the number of troops the enemy deployed to column ~i~.

Output Specification

Output the number of breaks achieved by Napoleon and the enemy separated by a space under Napoleon's optimal deployment.
Java solutions are encouraged to use fast input reading.

Sample Input

7
10
1 1 2 0 2 0 0 0 0 0

Sample Output

6 3

Explanation

The optimal arrangement is 0 1 0 1 0 1 1 1 1 1. This breaks through 6 columns and blocks 1 of the enemy's columns.