온라인 달걀 판매

경래는 닭을 기르고 있으며, 이번 겨울에 달걀이 많이 생산되어 온라인 장터에 팔려고 한다.

경래에게는 달걀 N개가 있고, 잠재 고객은 M명이다. i번째 고객은 달걀 한 개를 최대 P_i원까지 지불할 수 있다고 했다.

경래는 한 고객에게 달걀을 두 개 이상 팔지 않기로 했다. 하나의 판매 가격 A를 정하면, P_i가 A 이상인 고객은 달걀 한 개를 산다. 다만 준비한 달걀 N개보다 많이 팔 수는 없다.

경래가 얻을 수 있는 수익을 최대로 하는 판매 가격을 정하자. 최대 수익을 만드는 가격이 여러 개라면 그중 가장 낮은 가격을 출력한다.

첫째 줄에 정수 N (1 ≤ N ≤ 1,000)과 M (1 ≤ M ≤ 1,000)이 주어진다.

다음 M개 줄의 i번째 줄에는 i번째 고객이 달걀 한 개에 지불할 수 있는 최대 가격 P_i (1 ≤ P_i ≤ 1,000,000)가 주어진다.

첫째 줄에 최대 수익을 만드는 가장 낮은 판매 가격과 그 가격으로 얻을 수 있는 최대 수익을 공백으로 구분해 출력한다.