Старе вино у нові пляшки
Пляшки з вином ніколи не заповнюють до кінця: невелика кількість повітря завжди повинна залишатись у горловині для забезпечення теплового розширення та стиснення. Якщо у пляшці залишити занадто мало повітря, то вино може розширитись і вибити корок. Якщо повітря буде занадто багато, то вино може скиснути. Таким чином кожна пляшка має мінімальну та максимальну допустиму місткість вина.
За заданим об'ємом вина та набором пляшок різної місткості потрібно визначити, які пляшки слід використовувати, щоб заливати у них вино від мінімальної до максимальної допустимої місткості, і при цьому розлити якомога більше вина.
Вхідні дані
Перший рядок кожного тесту містить два цілих числа: кількість вина, що розливається (у літрах від 0 до 1000000), та кількість розмірів пляшок (від 1 до 100). Для кожного розміру пляшки задається один рядок, який описує її мінімальну та максимальну місткість у мілілітрах. Максимальна міскість не менше 325 мілілітрів і не більше 4500 мілілітрів. Мінімальна місткість не менше 95% і не більше 99% максимальної місткості. Відомо, що є у наявності нескінеченна кількість пляшок кожного типу.
Вихідні дані
Вивести одне ціле число: кількість вина у мілілітрах, яке не можна буде розлити.