ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2004 Round 1

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Stable Construction

Time limit: 0.5 second
Memory limit: 64 MB
As they say, every man must build a house, plant a tree, and grow a son during his life. So a programmer Vasechkin decided not to stay behind and to start building his own house. Vasechkin knew that his taste was not bad and thus he himself decorated the facade with brickwork. He carefully attached each brick with cement solution to a vertical wall. The result was very nice. Each brick was placed horizontally and lay on no more than one brick from the lower row. Vasechkin finished his work and thought. The time would pass and the cement solution between the bricks would crack. And one would like this beauty to remain for ages. So would it be stable even without the cement? It is necessary to perform complicated calculations, taking into consideration that all bricks have the same height, density, and width, but different lenghts. Also, a brick (or a system of bricks) with center of gravity on the edge of its support or outside it is considered to be unstable.


The first line contains an integer H, which is the number of brick rows, i.e., the height of the wall (1 ≤ H ≤ 10000). Then the disposition of bricks in the rows is given, row by row, beginning from the topmost one. For each row, there is a line containing an integer K, which is the number of bricks in this row (0 ≤ K ≤ 1000); each of the next K lines contains two integers Li and Ri, which are the coordinates of the left and right edges of the i-th brick. It is known that Li < Ri < Li+1 and 0 ≤ Li, Ri ≤ 10000. The number of all bricks is between 1 and 100 000.


You should write a program that outputs “Yes” if all the bricks are stable and “No” otherwise.


10 20
1 7
13 17
100 200
0 20
60 160
Problem Author: Idea - Alexey Lakhtin, prepared by Alexey Lakhtin
Problem Source: VIII Collegiate Students Urals Programming Contest. Yekaterinburg, March 11-16, 2004
To submit the solution for this problem go to the Problem set: 1311. Stable Construction