АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1325. Balloons

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

 

A grid of shelves containing k balloons is attached to the wall. The position of each balloon is defined by integer coordinates: xi is the column number in the shelf grid and yi is the row number; 1 £ i £ k. Student Vanya wants to gather all the balloons. In order to reach the balloons, he uses blocks that may be stacked on top of one another against the wall. Assume that the stock of blocks is unlimited.

Vanya can reach a balloon if he stands on a block that is located in the same column with the balloon, but one row below it. For example, if the balloon is in the sixth row it can be reached using a stack of five blocks.

Vanya attempts to place blocks against the wall so that he will be able to gather all the balloons going from left to right. On each step he can climb up or down at most 1 block. The starting position is the cell on level 0 before the wall.

Write a program to determine if it is possible to place blocks against the wall so that all the balloons will be reachable.

шарики copy

Limitations

k , xi, yi are integer numbers; 1 £ k £ 10,000; 1 £ xi, yi £ 10,000; xj < xj+1; 1 £ i £ k; 1 £ j < k.

Input

The first line of the input file contains an integer k, the number of balloons on the shelves. The following k lines define the positions of the balloons xi, yi (column numbers xi are given in ascending order).

Output

The output file should contain a single word (without quotation marks): “YES” if it is possible to place blocks against the wall allowing to gather all the balloons, or “NO” otherwise.

Example

Input

Output

4

2 2

5 4

7 2

8 3

YES

2

2 2

3 5

NO

1

1 2

YES

1

1 3

NO

 

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Чемпионат ACM / Рыбинск-2014 /
1325. 1326. B - Intellect Ltd 1327. C - Race Condition 1328. D - Ingress
 
время генерации 0.078 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.