Задачи
Старое вино в новые бутылки
Старое вино в новые бутылки
\includegraphics{https://static.e-olymp.com/content/99/99638061bc05405c8f28d0412b2b1ca8180b55ed.jpg}
Винные бутылки никогда не заполняют до конца: небольшое количество воздуха всегда должно оставаться в горлышке для обеспечения теплового расширения и сжатия. Если в бутылке оставить слишком мало воздуха, то вино может расшириться и выбить пробку. Если воздуха будет слишком много, то вино может испортиться. Таким образом каждая бутылка имеет минимальную и максимальную допустимую емкость вина.
По заданному объему вина и набору бутылок различного размера следует определить, какие бутылки следует использовать, чтобы заливать в них вино от минимальной до максимальной допустимой емкости, и при этом разлить как можно больше вина.
\InputFile
Первая строка каждого теста содержит два целых числа: количество разливаемого вина (в литрах от \textbf{0} до \textbf{1000000}) и количество размеров бутылок (между \textbf{1} и \textbf{100}). Для каждого размера бутылки задается одна строка, описывающая ее минимальную и максимальную вместимость в милилитрах. Максимальная вместимость не менее\textbf{ 325} милилитров и не более \textbf{4500} милилитров. Минимальная вместимость не менее \textbf{95}\% и не более \textbf{99}\% максимальной вместимости. Известно, что имеется бесконечное количество бутылок каждого типа.
\OutputFile
Вывести одно целое число: количество вина в миллилитрах, которое нельзя будет разлить.
Входные данные #1
10 2 4450 4500 725 750
Выходные данные #1
250