يحتاج 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