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.
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
|
