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ă un număr minim de misiuni, iar visul lui este să ajungă la un nivel cel puţin egal cu m.
Cerinţă
Determinaţi numărul minim de misiuni ce trebuie să fie alese pentru a ajunge la un nivel cel puţin egal cu m.
Date de intrare
Fişierul de intrare joc3.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 dintre 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 joc3.out conţine o singură linie pe care va fi scris numărul minim de misiuni ce trebuie să fie alese pentru a ajunge la un nivel cel puţin egal cu m.
Restricţii
0 < n,m ≤ 20000000000
2 < k ≤ 5000
Se consideră că cel puţin un nivel este accesibil eroului!
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.
3 5 100
1 2
2 9
7 19
29 80
77 190
2
Viorel alege pentru eroul lui 2 misiuni şi ajunge la nivelul 19. Misiunile alese sunt: (2,9) şi (7,19).
5 4 20
1 3
9 20
2 10
19 44
2
Viorel alege pentru eroul lui 2 misiuni şi ajunge la nivelul 20. Misiunile alese sunt: (2,10) şi (9,20).