eolymp
bolt
Try our new interface for solving problems
Problems

Программирование – это искусство!

Программирование – это искусство!

\textit{На вопрос слушателей Зимней Школы 2011: какая у него заработная плата, Пётр Митричев ответил очень политкорректно:} \textit{-- По сравнению с }\textbf{L}\textit{ -- много, а вот в сравнении с }\textbf{R}\textit{ ­-- мало.} \textit{О том, кто же такие были эти загадочные }\textbf{L}\textit{ и }\textbf{R}\textit{, Пётр дипломатично умолчал…} \includegraphics{https://static.e-olymp.com/content/6e/6e1f371b5b12ce8be733ea716ced8c41155ab7fb.jpg} Задумываясь над тем, что бы такого интересного рассказать слушателям Зимней Школы 2011 в г. Харькове, Пётр усиленно перебирал возможные варианты тематики, но практически сразу их отбрасывал, так как темы всегда приходили на ум уже давно известные и кем-то ранее рассказанные. Но как истинный художник-программист, свободно владеющий фигурами высшего пилотажа в этом деле, он не мог себе позволить выбрать какую-то ординарную тему. \textit{А расскажу я им об }\textbf{L}\textit{ и }\textbf{R}\textit{ ­-- тем более, что об этом, кажется, ещё никто не рассказывал}, -- подумал Пётр и начал рисовать план лекции и набрасывать схемы задачек. Благо в фирме, где он работал, был большой запас маркеров разных цветов, и схемы он начал рисовать именно ими. Если ему что-то в схеме не нравилось, Пётр поступал очень просто: он брал маркер другого цвета и зарисовывал им непонравившееся ему месту сверху новым цветом, соответствующему новому пункту плана. Перерисовывая таким образом схему, он очень быстро заметил, что и этот процесс можно предложить в виде задачки. Некий программист использует для рисования на координатной прямой \textbf{N} отрезков \textbf{N} маркеров разных цветов. Зная левые (\textbf{L}) и правые (\textbf{R}) концы каждого нарисованного отрезка, определить максимальное количество разных цветов, которые можно получить в окончательном варианте рисунка. Это количество назовём уровнем этого художника-программиста. \InputFile В первой строке входного файла задано натуральное число \textbf{N }(\textbf{1} ≤ \textbf{N} ≤ \textbf{300}). В последующих \textbf{N} строках задано \textbf{N} пар чисел \textbf{L} и \textbf{R} через пробел (\textbf{-10^9} ≤ \textbf{L_i} < \textbf{R_i} ≤ \textbf{10^9}). \OutputFile Вывести единственное число: искомый наибольший уровень художника-программиста.
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
4
1 3
2 4
2 3
1 4
Output example #1
3