Широко известна следующая задача для младших школьников. Три черепахи ползут по дороге. Одна черепаха говорит: “Впереди меня две черепахи”. Другая черепаха говорит: “Позади меня две черепахи”. Третья черепаха говорит: “Впереди меня две черепахи и позади меня две черепахи”. Как такое может быть? Ответ: третья черепаха врет!
По дороге одна за другой движутся N черепах. Каждая черепаха говорит фразу вида: “Впереди меня a
i черепах, а позади меня b
i черепах”. Ваша задача определить самое большое количество черепах, которые могут говорить правду.
Входные данные
В первой строке вводится целое число N (1 ≤ N ≤ 10000) . Далее следуют N строк, содержащих целые числа ai и bi, по модулю не превосходящие 10000, описывающие высказывание i-ой черепахи.
Данные о высказываниях черепах приведены в произвольном порядке, то есть первое высказывание не обязательно соответствует черепахе, идущей во главе колонны, второе - не обязательно следующей за ней и так далее
Выходные данные
Выведите целое число M – максимальное количество черепах, которые могут говорить правду.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
2 0
0 2
2 2 |
2 |