Фермер Джон хочет купить новых коров! На продаже имеется N (1 <= N <= 50,000) коров, а у ФД может потратить не более, чем M (1 <= M <=10^14) единиц денег. Корова I стоит Pi денег (1 <= Pi <= 10^9). У ФД имеется K купонов (1<=K<=N). Когда он использует купон для покупки коровы I, то цена будет Ci вместо Pi (1<=Ci<=Pi). Для каждой коровы ФД должен использовать ровно один купон.
Какое максимальное количество коров может купить ФД?
PROBLEM NAME: coupons
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа: N, K, M.
* Строки 2..N+1: Срока i+1 содержит два целых числа: Pi Ci.
Формат выходных данных
* Строка 1: Одно целое число, максимальное количество коров, которое может купить ФД.
Примечание
ФД использует купон при покупке коровы 3 и купит коров 1, 2, 3 за цену 3 + 2 + 1 = 6.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1 7
3 2
2 2
8 1
4 3
|
3
|