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