Problem C
Bobbin Hood

PublicDomainArchive, CC0 via Pixabay

Robin Hood var kjent for å ta fra de rike og gi til de fattige. Bobbin har lyst på å begynne å stjele også, men han skal bruke alle pengene på å kjøpe seg et sommerhus ved stranden. Han regner med å ende opp med å bli kalt “Bobbin Hood, som tar fra de som har mellom $X$ og $Y$ kroner, og beholder pengene selv.” For at han ikke skal virke for grådig så ønsker han å minimere verdien $Y-X$, slik at det ikke virker som at han stjeler så veldig mye. Han har allerede skaffet skattelistene som forteller ham hvor mye penger alle i landet har, og funnet ut hvor mye sommerhuset han ønsker seg koster.

Input

Første linje inneholder et heltall $P$, prisen på sommerhuset Bobbin vil kjøpe. Neste linje inneholder et heltall $N$, antall personer Bobbin kan stjele fra. De neste $N$ linjene inneholder ett heltall $F_ i$ hver, formuen til person $i$.

Output

To heltall, $X$ og $Y$ slik at differansen $Y-X$ er minst mulig, og at Bobbin har råd til sommerhuset ved å bare stjele fra folk som har mellom $X$ og $Y$ kroner (inklusivt). Dersom det finnes flere slike tallpar, gi det hvor $X$ er størst mulig.

Det vil alltid finnes en løsning.

50
6
11
25
13
17
10
15

11 17