The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Codeforces Round 113 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

graph matchings

greedy

sortings

two pointers

*2500

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Shoe Store

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe warehouse in your shop has *n* shoe pairs. Each pair is characterized by two integers: its price *c*_{i} and its size *s*_{i}. We know that on this very day all numbers *s*_{i} are different, that is, there is no more than one pair of each size.

The shop has *m* customers who came at the same time. The customer number *i* has *d*_{i} money and the size of his feet equals *l*_{i}. The customer number *i* can buy the pair number *j*, if *c*_{j} ≤ *d*_{i}, and also if *l*_{i} = *s*_{j} or *l*_{i} = *s*_{j} - 1; that is, it is necessary that he has enough money to pay for the shoes. It is also necessary that the size of his feet equals to or is less by 1 than the size of the shoes he chooses.

Your task is to sell some customers pairs of shoes (a pair per person) so as to maximize the sum of the sold pairs *c*_{j} that is, the profit. It is guaranteed that each customer buys no more than one pair and each pair will be bought by no more than one customer.

Input

The first input line contains the only integer *n* (1 ≤ *n* ≤ 10^{5}) — the number of shoe pairs in the warehouse. Then *n* lines contain the descriptions of pairs of shoes as two integers *c*_{i} and *s*_{i} (1 ≤ *c*_{i}, *s*_{i} ≤ 10^{9}), the numbers are separated by a space. It is guaranteed that all numbers *s*_{i} are different.

The next line contains an integer *m* (1 ≤ *m* ≤ 10^{5}) — the number of customers in the shop. Next *m* lines contain the customers' descriptions as two integers *d*_{i} and *l*_{i} (1 ≤ *d*_{i}, *l*_{i} ≤ 10^{9}), the numbers are separated by a space.

Output

In the first line print the only integer — the maximum profit you can get from selling shoes. In the second line print an integer *k* — the number of shoe pairs you will sell. In the following *k* lines print the descriptions of the sold pairs — two space-separated integers where the first number is the customer's number and the second number is the number of the shoes the customer will buy.

You can print pairs of numbers "the customer's number and the shoes' number" in any order, the customers and the pairs of shoes are numbered starting from 1 in the order in which they are given in the input. If there are several optimal answers, you are allowed to print any of them.

Please do not use the %lld specificator to read or write 64-bit numbers in С++. It is preferred to use the cin, cout streams or the %I64d specificator instead.

Examples

Input

3

10 1

30 2

20 3

2

20 1

20 2

Output

30

2

2 3

1 1

Input

3

10 4

20 5

30 6

2

70 4

50 5

Output

50

2

2 3

1 2

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/25/2024 11:44:28 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|