Üzemanyag-spórolás

Egy K kilométeres útra autót béreltünk, amelyet L liter benzinnel feltankolva kaptunk meg. Útközben N helyen tankoltunk, minden tankolás esetén nyilvántartva azt, hogy az indulástól számolva milyen messze és hány liter benzint tankoltunk. Az autó fogyasztása kilométerenként F liter. A benzin – az indulásnál a tankban lévő és a menet közben tankolt benzinnek köszönhetően – az út végéig garantáltan elegendő.

A standard bemenet első sora tartalmazza K, L, N és F értékét, mindegyikük pozitív egész szám. Az első sort követő N sor mindegyikében két egész szám szerepel, egymástól pontosan egy szóköz karakterrel elválasztva: a tankolásoknak az indulástól mért távolsága (km-ben számolva) és a tankolt benzin mennyisége (literben megadva).

Írjon programot, amely meghatározza, hogy mi annak a legkorábbi benzinkútnak a sorszáma, amely után már nem kellett volna tankolni a célba éréshez! Ha már a kezdeti feltöltéssel is megtehető az út, akkor ez az érték 0 legyen! Ezt az értéket a standard kimenet első és egyetlen sorában jelenítse meg! Ne feledje a sort soremelés karakterrel zárni!

1. példa bemenet

1. 100 300 3 5
2. 25 25
3. 50 75
4. 75 100

letöltés szöveges állományként

Az 1. példa bemenethez tartozó kimenet

1. 3

letöltés szöveges állományként

2. példa bemenet

1. 100 500 3 5
2. 25 50
3. 50 50
4. 75 50

letöltés szöveges állományként

A 2. példa bemenethez tartozó kimenet

1. 0

letöltés szöveges állományként

Megjegyzés

Ez a feladat nem saját találmány, ötlete és szövege nagyrészt a http://nemes.inf.elte.hu/nemes_archivum.html oldalról letölthető http://nemes.inf.elte.hu/2016/nt16-1f2.doc állomány első feladatán alapul.