eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Расписание вечеринок

Расписание вечеринок

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Вы только что получили еще один счет, который не в состоянии оплатить из-за нехватки денег. К сожалению, это произошло уже не в первый раз, поэтому Вы решили расследовать причины своего постоянного денежного затруднения. Причина была достаточно банальной: львиная доля денег обычно исчезала на вечеринках.

Вы начали думать, как решить проблему там, где она возникает - а именно на самих вечеринках. Вы решили ввести лимит на бюджет вечеринок, при этом получая от них максимальное удовольствие.

Вы заранее узнали величину вступительного взноса для каждой вечеринки и оценили количество удовольствия, которое сможете получить там. Этот список был составлен легко, но как подобрать вечеринки, на которых Вам будет наиболее интересно, и которые суммарно не будут превышать Ваш бюджет?

Напишите программу, которая найдет оптимальное подмножество вечеринок, на которых будет наиболее весело. Имейте в виду, что использовать полностью весь бюджет не обязательно. Достигните наибольшего веселья, не превысив при этом бюджет.

Входные данные

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

Входные данные содержат несколько тестов. Последняя строка содержит 0 0 и не обрабатывается.

Выходные данные

Для каждого теста вывести в отдельной строке суммарное значение стоимостей входных билетов на вечеринки, а также общую сумму полученного удовольствия. Выводимые числа следует разделять пробелом.

Пример

Входные данные #1
50 10
12 3
15 8
16 9
16 6
10 2
21 9
18 4
12 4
17 8
18 9
50 10
13 8
19 10
16 8
12 9
10 2
12 8
13 5
15 5
11 7
16 2
0 0
Выходные данные #1
49 26
48 32