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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ M ≤ 1000

1 < N ≤ 10⁵

1 ≤ N_i ≤ M

1 ≤ S_i ≤ 1000

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

100
6
30 50
70 200
50 300
30 40
100 700
30 30

700