온라인 달걀 판매
면접 대비시간 제한2초메모리 제한128 MB
달걀 N개와 M명의 구매 희망가가 주어질 때, 해당 가격 이상인 고객이 모두 구매하되 최대 N개까지 팔 수 있는 상황에서 수익을 최대화하는 가격(동일하면 가장 낮은 가격)을 구합니다.
문제
경래는 닭을 기르고 있으며, 이번 겨울에 달걀이 많이 생산되어 온라인 장터에 팔려고 한다.
경래에게는 달걀 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)가 주어진다.
출력
첫째 줄에 최대 수익을 만드는 가장 낮은 판매 가격과 그 가격으로 얻을 수 있는 최대 수익을 공백으로 구분해 출력한다.