Входной файл: | Стандартный вход | Ограничение времени: | 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 |
|
|