Cerința

Dorești să faci un parfum pentru care vei avea nevoie de X petale de flori. În grădina ta sunt N tipuri de flori, fiecare cu un anumit număr de petale, notat cu count[i]. Odată la T zile, toate florile își vor scutura petalele, urmând ca tu să le colectezi. De asemenea, florile tale au fiecare câte o durată de viață exprimată în zile, notată cu days[i]. Odată ce o floare moare, ea nu mai produce petale.
Acum, te ești interesat să găsești valoarea maximă a lui T pentru care s-ar strânge minim X petale de flori după primele Z zile.

Date de intrare

Programul citește de la tastatură numerele N, X și Z. Pe umrătoarele N linii se află câte o pereche de valori de forma count[i], days[i].

Date de ieșire

Programul va afișa pe valoarea maximă a lui T pentru care se poate produce parfumul după Z zile.

Restricții și precizări

• 1 ≤ N ≤ 100 000
• 1 ≤ count[i] ≤ 1 000 000 000
• 1 ≤ days[i] ≤ 1 000 000 000
• 1 ≤ X ≤ 1 000 000 000
• 1 ≤ Z ≤ 1 000 000 000
• Se garantează că T maxim este cel mult 1 000 000 000.

Exemplu:

Intrare

4 20 7
4 5
10 2
6 4
2 10

Ieșire

2

Explicație

La momentul de timp 2 culegem 4 + 10 + 6 + 2 = 22 de petale.
La momentul de timp 4 vom culege alte 4 + 6 + 2 = 12 petale.
La momentul de timp 6 vom culege alte 2 petale.
În total, vom fi cules 22 + 12 + 2 = 36 de petale.
Se poate demonstra că nu există T ≥ 2 astfel încât să se poate culege minim 20 de petale până în ziua 7.