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 Regional School Programming Contest 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Uncle Styopa and Buses

Time limit: 1.0 second
Memory limit: 64 MB
The local government provided funds for repairing a section of the Big Vasyuki–Small Vasyuki motorway. This is a two-lane road, so it was decided to close one lane for repairs at first and leave the other lane for traffic in both directions.
The cars going in opposite directions have to take turns in passing this section of the road. Naturally, traffic jams accumulated quickly at both ends of the section. Officer Uncle Styopa was assigned to control traffic here. He was lucky to find a couple of decent country roads and put “Detour” signs where necessary. The problem seemed to be solved.
However, it turned out that country roads were not good enough for buses traveling between Big Vasyuki and Small Vasyuki. Fortunately, buses run according to their schedule, so Uncle Styopa knows in advance when and from which direction a bus will come. He also knows the maximal time each bus may spend passing the road section under repair without being late for its destination. Help Uncle Styopa organize the process so that all the buses are in time at their destinations.
A bus may enter the only free lane only if there are no other buses on it. It takes exactly one minute for any bus to pass the road section under repair.


The first line contains the number of buses n from Small Vasyuki to Big Vasyuki (1 ≤ n ≤ 100000). These buses are described in the following n lines in the form of pairs of integers ti and pi (1 ≤ ti, pi ≤ 108), where ti is the time in minutes when the arrival of the ith bus is expected and pi is the maximal number of minutes this bus may spend passing the road section under repair. Then there is a line with the number of buses m going from Big Vasyuki to Small Vasyuki (1 ≤ m ≤ 100000). The following m lines contain their description in the same format.
The buses are described in the order in which they come to the road section under repair. The buses running in one direction should pass the section under repair in the same order they approach it.


Output “YES” if Uncle Styopa can organize the traffic so that no bus is late and output “NO” otherwise.


1 1
1 2
2 2
1 1
1 2
2 1
Problem Author: Eugene Kurpilyansky
Problem Source: Ural Regional School Programming Contest 2010
To submit the solution for this problem go to the Problem set: 1791. Uncle Styopa and Buses