O masina porneste din pozitia 0 cu o cantitate initiala de combustibil (exprimata in kilometri posibili de parcurs) si trebuie sa ajunga la o destinatie aflata la distanta D. Pe traseu exista n statii de realimentare, fiecare la o pozitie data, unde masina poate alimenta (o singura data) o cantitate data de combustibil, daca ajunge la acea statie. Determinati, folosind metoda Greedy, numarul minim de opriri pentru realimentare necesare pentru a ajunge la destinatie, sau -1 daca aceasta nu este posibila.
- Date de intrare
- Pe prima linie se citesc D, combustibilul initial si n. Urmeaza n linii, fiecare cu doua numere: pozitia unei statii si cantitatea de combustibil pe care o ofera.
- Date de iesire
- Se afiseaza un singur numar: numarul minim de opriri, sau -1 daca destinatia nu poate fi atinsa.
- Restrictii
- 1 <= n <= 100000, 0 <= combustibil initial, D <= 10^9, statiile sunt date in ordinea pozitiilor
Exemple
Exemplul 1
Intrare
100 10 4 10 60 20 30 30 30 60 40
Iesire
2
Exemplul 2
Intrare
1 1 0
Iesire
0