Ограничение по времени: 500 ms Ограничение по памяти: 256 Mb
Фермер Джон хочет купить новых коров! На продаже имеется 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.
Ваш ответ: