Задача E. Иглу

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

Исследователи Арктики строят иглу из снежных блоков. Для этого им нужно доставить прямоугольные блоки для постройки на строительную площадку. Всего можно заготовить N блоков. Каждый блок имеет вес Mi килограмм и объем Siм3 (в зависимости от плотности), а сами блоки доставляются санями с грузоподъемностью M килограмм. Сани могут везти блоки любого размера. Время доставки блоков санями до места стройки составляет T минут и не зависит от количества погруженных на них блоков.

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

Напишите программу для решения этой задачи!

Формат входных данных

Первая строка содержит целое число M – грузоподъемность саней.

Вторая строка содержит единственное целое число N – количество блоков.

Следующие N строк содержат по два целых числа Mi, и Si – вес и объем i-того блока.

Формат выходных данных

Выведите единственное целое число S - наибольший объем доставленных блоков.

Ограничения

1 ≤ M ≤ 1000

1 < N ≤ 105

1 ≤ Ni ≤ M

1 ≤ Si ≤ 1000

Примеры тестов

Стандартный вход Стандартный выход
1
100
6
30 50
70 200
50 300
30 40
100 700
30 30
700

0.074s 0.014s 13