Maximum Shelves Used for Items Placement

You are given n shelves, each with a weight capacity and a maximum allowable item height. You are also given m items, each defined by its weight and height requirement. Your task is to place the first k items (in the given order) onto the shelves.

For each item, you should try to place it on the shelves in increasing order of the shelf's weight capacity. An item can be placed on a shelf if:

• The sum of the weights of items already placed on that shelf plus the current item's weight does not exceed the shelf's capacity.
• The item's height is less than or equal to the shelf's maximum allowed height.

Once an item is placed, update the cumulative weight on that shelf and move on to the next item. The answer is defined as the maximum number of shelves used, i.e. the 1-indexed position of the last shelf that received an item.

Note: If k is 0, then no item is placed and the answer is 0.

The placement condition for an item with weight \(w\) and height \(h\) on a shelf with capacity \(C\) and height limit \(H\) can be written in LaTeX as:

[ L + w \leq C \quad \text{and} \quad h \leq H, ]

where \(L\) is the current load on the shelf.

inputFormat

The input is given via standard input (stdin) in the following format:

n
capacity_1 height_1
capacity_2 height_2
... (n lines for shelves)

m
weight_1 height_1
weight_2 height_2
... (m lines for items)

k

Here, n is the number of shelves, followed by n lines each containing two integers (the shelf's weight capacity and maximum item height). Then, m denotes the number of items, followed by m lines each containing two integers (the item's weight and height requirement). Finally, k specifies the number of items (from the beginning of the items list) that you need to place.

outputFormat

Output via standard output (stdout) a single integer representing the maximum number of shelves used after trying to place the first k items.

## sample

5
100 50
200 75
150 60
180 100
120 80
6
50 40
70 50
80 60
60 45
90 70
40 35
4

3