Resource Allocation for City Rebuilding

In this problem, you are given multiple test cases. For each test case, there are a number of cities and a sequence of resource shipments. Each city requires a certain amount of resources to be ready for rebuilding. Shipments are processed in order and allocated to the first city (based on input order) that still requires resources. A shipment is used to try to satisfy a city’s resource requirement. If a shipment's available resources are greater than or equal to the remaining required resources of the city, the city's requirement is completely met, and any leftover resources in the shipment are discarded. Otherwise, the shipment partially fulfills the city’s requirement, and the shortage remains for future shipments. The goal is to determine, for each test case, the number of cities that have been fully satisfied (i.e. become ready for rebuilding).

More formally, let (c) be the number of cities with initial required resources (r_i) and let there be (s) shipments each with resource amount (a_j). For each shipment in order, allocate it to the first city (in the order of appearance) whose remaining requirement is more than zero. If (a_j \ge r_i), then that city is considered finished ((r_i = 0)); otherwise, reduce (r_i) by (a_j). Report the total count of cities that have been completely satisfied for each test case.

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains an integer (T) representing the number of test cases. For each test case:

• The first line contains two integers (c) and (r) separated by a space, where (c) is the number of cities and (r) is the number of shipment records.
• The next (c) lines each contain two integers: the city identifier and the required resources for that city.
• The following (r) lines each contain two integers: the shipment identifier and the available shipment resources.

Note: City identifiers and shipment identifiers are provided for reference, but shipments are allocated in the order in which cities appear in the input.

outputFormat

For each test case, output a single integer on a new line representing the number of cities that are fully supplied and ready for rebuilding.## sample

3
2 3
1 30
2 50
1 20
2 40
3 30
1 2
1 20
1 10
2 10
3 3
1 5
2 5
3 10
1 5
2 5
3 10

1
1
3