«0/1» у назві задачі виражає, що кожен предмет можна лише або взяти (1 шт.), або ні (0 шт.), ніяких інших варіантів нема.

Є рюкзак місткістю (вантажопідйомністю) ~M~ грамів. Є ~N~ предметів, кожен з яких неподільний:

• перший важить ~m_1~ грамів і коштує ~c_1~ грн;
• другий важить ~m_2~ грамів і коштує ~c_2~ грн;
• ... і так далі ...,
• до ~N~-ого, який важить ~m_N~ грамів і коштує ~c_N~ грн.

Можна вибирати, які з предметів узяти в рюкзак, а які не взяти, але конкретний предмет можна лише або взяти, або ні, а взяти частину предмета не можна.

Яку найбільшу сумарну вартість цих предметів можна набрати, не перевищивши місткість рюкзака? (Інакше кажучи, сума мас вибраних предметів мусить бути не більшою ~M~).

Вхідні дані

Перший рядок містить «вантажопідйомність» рюкзака ~M~. Другий рядок містить кількість предметів ~N~. Кожен з подальших ~N~ рядків містить спочатку масу відповідного предмету ~m_i~, потім (через пробіл) його вартість ~с_i~.

Значення ~M~ та ~m_i~ вимірюються у грамах, значення ~c_i~ – у копійках, значення ~N~ – у штуках (безрозмірне).

Результати

Ваша програма повинна вивести єдине число – максимальну можливу вартість (у копійках) вибраних предметів.

Обмеження та особливості оцінювання

В рамках дисципліни «Алгоритми та структури даних» для студентів ФОТІУС очікується, що студенти писатимуть програму за принципом «реалізувати як методи (підпрограми) кілька різних алгоритмів, і вирішувати, який з них викликати, залежно від вхідних даних». Конкретні обмеження наведені в ось цій таблиці:

Нема вимоги писати обов'язково окрему програму для кожного з цих 6 блоків. Тим паче, що лише дуже дивна програма зможе, наприклад, проходити блок 4, але не проходити блоки 1, 2 і 3, бо всі обмеження в блоках 1, 2 і 3 менші, чим у блоці 4.

Але порівняємо, наприклад, блок 3 і блок 5. Обмеження на ~M~, ~m_i~ та ~c_i~ у блоці 3 (до ~10^5~) значно менші, чим у блоці 5 (до ~10^{15}~). Але обмеження на ~N~ у блоці 3 (до 100) помітно більше, чим у блоці 5 (до 15). Так і виходить, що цілком може бути один «алгоритм для блоку 3», який може працювати при відносно великих ~N~, але йому важливо, щоб були малими ~M~, ~m_i~ та ~c_i~, і інший «алгоритм для блоку 5», який може працювати з будь-якими ~M~, ~m_i~ та ~c_i~ (наприклад, поки вони поміщаються в тип long), але він працює адекватно лише для малих ~N~ (до 15 йому нормально, а до 100 вже надто багато).

Я знаю щонайменше два алгоритми, які вміють обробити відразу всі ці блоки, але вони обидва надто складні для дисципліни «Алгоритми та структури даних» на ФОТІУС. причому один з тих алгоритмів я вмію програмувати лише мовами C++ та Java, а ні в C#, ні в Python просто нема потрібної бібліотечної структури даних. А написати різні алгоритми для різних блоків значно легше, хоч і може бути трохи громіздкувато.

Кожен зі згаданих у таблиці блоків зараховується, лише коли програма успішно проходить всі тести цього блоку. Водночас, блоки перевіряються незалежно. Наприклад, цілком можна пройти блок 2, не пройти жоден з блоків 3 і 4, далі пройти блок 5, далі нічого не пройти. Тоді за блоки&nbsp3, 4, 6 і 7 буде по 0 балів (навіть якщо програма пройшла якісь, але не всі, тести з цих блоків); зате бали за блоки 2 і 5 в такій ситуації будуть додані, це буде 20%+15%=35% балів).

Приклади

Вхід прикладу 1

5
3
1 600
2 1000
3 1200

Результат прикладу 1

2200

Вхід прикладу 2

50
4
10 600
20 1000
30 1200
49 2070

Результат прикладу 2

2200

Вхід прикладу 3

498
4
100 600
200 1000
300 1200
490 2070

Результат прикладу 3

2070