Обычный клиент банка Олег решает интересную шахматную задачу: расставить на шахматной доске n × n наибольшее число ладей, чтобы они не били друг друга.
Напомним, что ладья, которая стоит в клетке (a, b), бьет ладью, стоящую в клетке (x, y), тогда и только тогда, когда a = x или b = y.
К сожалению (или радости?) Олега ответ в этой задаче всегда получался равным n, поэтому вскоре задача ему наскучила. Он решил её усложнить, удалив некоторые клетки из шахматной доски. Удалив клетку, Олег подразумевает, что на нее нельзя ставить ладью, однако, бить «сквозь» удаленные клетки ладьи могут.
Олег удаляет клетки группами, а именно, он раз за разом выбирает некоторый прямоугольник по сторонами, параллельными осям координат, и удаляет все клетки в нем. Формально, если он выбрал некоторый прямоугольник, левая нижняя и правая верхняя клетки которого имеют координаты (x1, y1) и (x2, y2), соответственно, то он удаляет все такие клетки (x, y) что x1 ≤ x ≤ x2 и y1 ≤ y ≤ y2. Гарантируется, что никакую клетку два раза Олег удалять не будет, то есть все выбранные прямоугольники не пересекаются.
Эту версию задачи Олег решить не смог, а его друг, к которому он часто обращается за советами, — аналитик Игорь — сейчас очень занят на конференции, и не может помочь Олегу.
Вы — последняя надежда Олега! Помогите ему: по заданному размеру доски и прямоугольникам, клетки в которых удалены, выясните, какое максимальное число ладей можно расставить на доске так, чтобы никакая ладья не била никакую другую.