Hide

Problem C
Bobbin Hood

Languages en no
/problems/uib.bobbin/file/statement/no/img-0001.jpg
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 YX, 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 Fi hver, formuen til person i.

Output

To heltall, X og Y slik at differansen YX 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.

Sample Input 1 Sample Output 1
50
6
11
25
13
17
10
15
11 17
Hide