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