This page is still under construction.

Parts of this page are still being built. What you see may change.

Banana Box Purchases

Interview

Time limit2sMemory limit256 MB

Summary
Simulate Gru's account: at each shipping time buy if affordable, otherwise try to pay the higher price at delivery, and count purchases.
Level

Medium6 of 10

Topics
Simulation, Sorting, Greedy, Implementation
Solved
No attempts yet

Problem

Minions love bananas, so Gru constantly has to buy them. Since there are very many minions, he wants to know how many bananas he will buy.

He buys bananas from online stores that deliver to his home. This method has one special feature: if he pays for a box of bananas at the moment it is shipped, its price is C1, and if he pays at the moment it is received, its price is C2. Gru hacked the servers of all online banana stores and learned the sales data for the near future. Now he knows, for each box of bananas, when it can be shipped and when it will arrive to him. He also has a bank statement showing when and how much money will be credited to his account.

Gru is very impatient, so if he can buy a box of bananas at the moment it is shipped (he has money in his account and it is enough for the purchase), he buys it. Otherwise he calls a courier, and if at the moment of delivery Gru can pay for it, he buys the parcel, and if not, the courier leaves with nothing.

Besides the minions, Gru is raising three girls, so he has no time for calculations. He asks you to write a program that, from the data he has, computes how many boxes of bananas he will end up buying.

Input

The first line contains two integers C1 and C2 (1 ≤ C1 ≤ C2 ≤ 1000), the price of a box of bananas at the moment of shipping and at the moment of receiving. The second line contains a single integer n (1 ≤ n ≤ 100 000), the number of payments credited to Gru's account. The next n lines contain pairs of numbers ai, ti (1 ≤ ai ≤ 1000, 1 ≤ ti ≤ 109), the amount of money credited and the time when it is credited. The next line contains the number m (1 ≤ m ≤ 100 000), the number of boxes of bananas that will be sold in the near future. The next m lines contain pairs of numbers li, ri (1 ≤ li ≤ ri ≤ 109), the shipping time and the receiving time of each box of bananas.

For any i ≠ j, li ≠ lj, li ≠ rj, and ri ≠ rj hold.

Output

In the single line of the output file, print the number of boxes of bananas that Gru can buy.

Examples1

  1. Example 1

    Input
    100 200
3
100 1
200 10
400 21
4
12 22
2 4
5 23
8 19
    Expected output
    3