Farmer John צריך פרות חדשות! יש $N$ למכירה, $1 \le N \le 50,000$, ו־FJ אינו רשאי לעבור את התקציב $M$, $1 \le M \le 10^{14}$. פרה $i$ עולה $P_{i}$, $1 \le P_{i} \le 10^9$. יש לו $K$ קופונים, $1 \le K \le N$, וקופון לפרה $i$ משנה את המחיר ל־$C_{i}$, $1 \le C_{i} \le P_{i}$. רק קופון אחד לפרה.

כמה פרות לכל היותר יכול FJ לקנות?

קלט

• שורה $1$: שלמים $N$, $K$, $M$ מופרדים ברווחים.

• שורות $2..N+1$: שורה $i+1$ מכילה שלמים $P_{i}$ ו־$C_{i}$.

פלט

• שורה $1$: שלם, מספר הפרות המרבי שאפשר לקנות.

דוגמאות

קלט 1

4 1 7
3 2
2 2
8 1
4 3

פלט 1

3

הערה

ל־FJ יש $4$ פרות, קופון $1$ ותקציב $7$.

משתמש בקופון ל־$3$ וקונה $1$, $2$, $3$ במחיר $3 + 2 + 1 = 6$.

מחברי הבעיה: Neal Wu ו־Mark Gordon, 2012