Инна очень любит спать, поэтому, чтобы проснуться, ей нужно целых n будильников. Представим, что комната Инны — это квадрат 100 × 100 с левым нижним углом в точке (0, 0), а правым верхним в точке (100, 100). Тогда будильники — это точки с целочисленными координатами в этом квадрате.
Наступило утро. Все n будильников в комнате Инны уже звонят, поэтому Инна очень хочет выключить их. Для этого Инна придумала занимательную игру:
- Сначала Инна выбирает тип отрезков, которые она будет использовать в течение всей игры. Отрезки могут быть либо вертикальные, либо горизонтальные.
- Затем Инна делает несколько ходов. За один ход Инна может нарисовать на плоскости отрезок любой длины, выбранного в начале игры типа (либо вертикальный, либо горизонтальный), тогда все будильники, находящиеся на этом отрезке выключатся. Игра заканчивается, когда выключены все будильники.
Инна очень хочет спать, поэтому ей надо расправиться с будильниками как можно скорее. Помогите ей, найдите минимальное количество ходов в игре, которое требуется для выключения всех будильников!
Выходные данные
В единственной строке выведите целое число — минимальное количество отрезков, которые нужно будет нарисовать Инне, если она будет действовать оптимально.
Примечание
В первом примере Инна сначала выбирает тип «вертикальные отрезки», а затем рисует отрезки с концами: (0, 0), (0, 2); и, к примеру, (1, 0), (1, 1). Если она будет рисовать горизонтальные отрезки, понадобится как минимум 3 отрезка.
В третьем примере важно то, что Инна не имеет права менять тип отрезков во время игры. Поэтому ей потребуется либо 3 вертикальных, либо 3 горизонтальных отрезка, либо 3 вертикальных, чтобы закончить игру.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0 0
0 1
0 2
1 0
|
2
|
|
2
|
4
0 0
0 1
1 0
1 1
|
2
|
|
3
|
4
1 1
1 2
2 3
3 3
|
3
|