Лимит времени 2000/4000/4000/8000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
cheese
Пенсионерка Иванова внимательно следит за скидками и распродажами. Поэтому к моменту начала распродажи элитного сыра в магазине "Изыск" она уже точно знала, что хочет купить G граммов любимого продукта.
И вот настало утро распродажи. Иванова от входа рванула в сырный отдел, прибежала туда первой и умело закрыла изящным корпусом от конкурентов ящик с разнокалиберными кусками сыра, завёрнутыми в целлофан, с весом в граммах на этикетке. Оставалось только выбрать из N кусков те, которые в сумме дадут не больше G граммов (лучше, конечно, ровно G, но если не выйдет, то чуть меньше, но при этом побольше).
Разработайте программу, которая по данным о количестве и весе
кусков поможет Ивановой определить, сколько граммов сыра она сможет купить.
Входные данные. В первой строке - натуральные числа N (количество кусков) и G (максимальное количество граммов сыра, на которое у Ивановой хватит денег), разделённые пробелом, произведение их значений не превышает 1500000. Далее следуют N строк, в каждой из которых натуральное число, вес куска сыра в граммах. Куски очень разные, но точно не тяжелей 2 кг.
Выходные данные. Целое число - максимальный возможный вес сыра, который сможет купить Иванова.
Для отправки решений необходимо выполнить вход.
|