Расписание вечеринок
Вы только что получили еще один счет, который не в состоянии оплатить из-за нехватки денег. К сожалению, это произошло уже не в первый раз, поэтому Вы решили расследовать причины своего постоянного денежного затруднения. Причина была достаточно банальной: львиная доля денег обычно исчезала на вечеринках.
Вы начали думать, как решить проблему там, где она возникает - а именно на самих вечеринках. Вы решили ввести лимит на бюджет вечеринок, при этом получая от них максимальное удовольствие.
Вы заранее узнали величину вступительного взноса для каждой вечеринки и оценили количество удовольствия, которое сможете получить там. Этот список был составлен легко, но как подобрать вечеринки, на которых Вам будет наиболее интересно, и которые суммарно не будут превышать Ваш бюджет?
Напишите программу, которая найдет оптимальное подмножество вечеринок, на которых будет наиболее весело. Имейте в виду, что использовать полностью весь бюджет не обязательно. Достигните наибольшего веселья, не превысив при этом бюджет.
Входные данные
Первая строка содержит величину общего бюджета и количество вечеринок n. Каждая из следующих n строк содержит два числа. Первое число указывает на стоимость входного билета на вечеринки. Стоимость вечеринок колеблется от 5 до 25 франков. Второе число содержит количество удовольствия, получаемого от посещения вечеринки - оно является целым от 0 до 10. Общий бюджет не превосходит 500, всего имеется не более 100 вечеринок. Все числа разделены одним пробелом.
Входные данные содержат несколько тестов. Последняя строка содержит 0 0 и не обрабатывается.
Выходные данные
Для каждого теста вывести в отдельной строке суммарное значение стоимостей входных билетов на вечеринки, а также общую сумму полученного удовольствия. Выводимые числа следует разделять пробелом.