Нина тренирует свою команду по баскетболу. Команда Нины состоит из \(n\) игроков, пронумерованных от \(1\) до \(n\). У \(i\)-го игрока есть интервал рук \([l_i,r_i]\). Два игрока \(i\) и \(j\) (\(i \neq j\)) могут передавать мяч друг другу, только если \(|i-j|\in[l_i+l_j,r_i+r_j]\) (здесь \(|x|\) обозначает абсолютное значение \(x\)).
Нина хочет проверить готовность своей команды. Для этого она проведет несколько раундов передач.
- В каждом раунде Нина выберет последовательность игроков \(p_1,p_2,\ldots,p_m\) такую, что игроки \(p_i\) и \(p_{i+1}\) могут передавать мяч друг другу для всех \(1 \le i < m\). Длина последовательности \(m\) может быть выбрана Ниной. Каждый игрок может появиться в последовательности \(p_1,p_2,\ldots,p_m\) несколько раз или вообще не появиться в ней.
- Затем Нина бросит мяч игроку \(p_1\), игрок \(p_1\) передаст мяч игроку \(p_2\) и так далее... Игрок \(p_m\) выбросит мяч за пределы баскетбольного поля, так что его больше нельзя будет использовать.
Как тренер, Нина хочет, чтобы каждый из \(n\) игроков участвовал хотя бы в одном раунде передач. Поскольку Нина хочет пойти на свидание после школы, она хочет, чтобы вы вычислили минимальное количество раундов передач, необходимых для выполнения задачи.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество раундов передач, которое Нина должна провести, чтобы завершить свою работу.
Примечание
В первых двух наборах входных данных Нина может провести два раунда передач: один с \(p=[1]\) и один с \(p=[2]\). Можно показать, что одного раунда передач недостаточно, поэтому ответ \(2\).
В третьем наборе входных данных Нина может провести два раунда передач: один с \(p=[1,3]\) и один с \(p=[2]\). Игрок \(1\) может передать мяч игроку \(3\), так как \(|3-1|=2 \in [1+1,3+3]\). Можно показать, что одного раунда передач недостаточно, поэтому ответ \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
1 1
1 1
2
1 1
2 2
3
1 3
1 3
1 3
5
1 1
2 2
1 5
2 2
1 1
6
1 2
5 5
2 3
2 3
2 2
1 2
|
2
2
2
1
3
|