Problem C
Bobbin Hood

PublicDomainArchive, CC0 via Pixabay

Robin Hood is known for stealing from the rich and giving to the poor. Bobbin, Robin’s brother, also want to steal. However, he wants to spend the money on a fancy beach house. He is expecting to be known as “Bobbin Hood, stealing from the ones with between $X$ and $Y$ NOK, and keeping the money.” To not make his reputation worse than necessary he wants to minimize the value $Y-X$, so that the range of money one needs to have to be robbed is as small as possible. He has already acquired the tax listings and hence he knows how much money every one in the county has.

Input

The first line of input contains an integer $1 \leq P \leq 2 \cdot 10^9$, the price of the beach house Bobbin wants to buy. The second line of input contains an integer $1 \leq N \leq 2 \cdot 10^6$, the number of people in the county. And last, the next $N$ lines contains integers $1 \leq F_ i \leq 2 \cdot 10^9$ giving the amount of money each of the $N$ people have. The sum of the $N$ integers will always be at least $P$, so that if Bobbin robs everyone, he can always afford the beach house.

Output

Two integers $X$ and $Y$ such that the difference $Y-X$ is minimized and such that Bobbin can steal money only from people with between $X$ and $Y$ money inclusively and afford the beach house. If there are several such pairs, give the one with the highest $X$ value.

50
6
11
25
13
17
10
15

11 17