joc

Viorel a primit de la părinţi un joc de strategie. Eroul jocului are la început un nivel iniţial $n$ şi trebuie să îndeplinescă anumite misiuni. Eroului $i$ se permite accesul la o misiune numai dacă nivelul său este cel puţin egal cu nivelul minim cerut de aceasta, iar după fiecare misiune îndeplinită nivelul său creşte la o anumită valoare, specifică misiunii respective.
După finalizarea unei misiuni Viorel alege altă misiune pentru eroul său, în condiţiile amintite.
Pentru că părinţii nu îl lasă să se joace prea mult, Viorel trebuie să aleagă $\underline{\text{un număr minim de misiuni}}$, iar visul lui este să ajungă la un $\underline{\text{nivel cel puţin egal cu} \ m}$.

Cerinţă

Determinaţi nivelul atins de erou după parcurgerea misiunilor alese şi numărul acestora.

Date de intrare

Fişierul de intrare joc.in conţine:

• pe prima linie trei numere naturale: $n$ (nivelul iniţial al eroului), $k$ (numărul de misiuni disponibile) şi $m$ (nivelul minim cerut pentru a termina jocul) separate prin câte un spaţiu
• fiecare din următoarele $k$ linii corespunde câte unei misiuni şi conţine două valori pozitive, separate printr-un spaţiu, reprezentând nivelul minim necesar începerii misiunii, respectiv nivelul dobândit de erou la finalizarea misiunii respective.

Date de ieşire

Fişierul de ieşire joc.out conţine pe o singură linie nivelul eroului şi numărul minim de misiuni alese, separate printr-un spaţiu.

Restricţii şi precizări

• $0 \lt n, m \leq 2 \ 000 \ 000 \ 000$
• $2 \lt k \leq 5 \ 000$
• Se consideră că cel puţin un nivel este accesibil eroului!

Exemplul 1

joc.in

6 10 25
1 3
2 3
1 2
2 6
3 9
2 10
5 8
10 17
15 27
17 24

joc.out

27 3

Explicaţie

Viorel alege pentru eroul lui de nivel $6$ următoarele misiuni: $(2, 10), (10, 17)$ şi $(15, 27)$ deci la sfârşit eroul lui are nivelul $27$, minim cerut pentru a câştiga jocul.

Exemplul 2

joc.in

3 5 100
1 2
2 9
7 19
29 80
77 190

joc.out

19 2

Explicaţie

Viorel alege pentru eroul lui $2$ misiuni şi ajunge la nivelul $19$. Misiunile alese sunt: $(2, 9)$ şi $(7, 19)$.

Exemplul 3

joc.in

5 4 20
1 3
9 20
2 10
19 44

joc.out

20 2

Explicaţie

Viorel alege pentru eroul lui $2$ misiuni şi ajunge la nivelul 20. Misiunile alese sunt: $(2, 10)$ şi $(9, 20)$.