Фермер Джон хочет сделать подарки своим N (1 <= N <= 1000) коровам, используя свой бюджет в B (1 <= B <= 1,000,000,000) единиц денег.
Корова I требует подарка с ценой P(i) единиц ценой доставки S(i) (поэтому для ФД будет стоить P(i)+S(i) заказать этот подарок). У ФД есть специальный купон, который он может использовать чтобы заказать подарок за полцены. Если ФД использует этот купон для коровы I, то он должен будет заплатить только P(i)/2 + S(i). По соглашению, все P(i) четные числа.
Пожалуйста, помогите ФД определить максимальное количество коров, которым он сможет сделать подарки.
PROBLEM NAME: gifts
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и B.
* Строки 2..1+N: Строка i+1 содержит два разделенных пробелом целых числа, P(i) и S(i). (0 <= P(i),S(i) <= 1,000,000,000, P(i)- четное)
Формат выходных данных
* Строка 1: Максимальное количество коров, которым ФД может купить подарки.
Примечание
ФД может купить подарки для коров с первой по 4-ую, если он использует Купон для коровы 3. Потраченная сумма будет: (4+2)+(2+0)+(4+1)+(6+3) = 22. Заметим, что ФД альтернативно может использовать купон для коров 1 или 4 И все равно не превысить бюджет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 24
4 2
2 0
8 1
6 3
12 5
|
4
|