Maximizing Fulfilled Orders

You are given an inventory of items where each item belongs to a certain product category. You are also given a list of order requests. Each order request specifies a product category and the quantity desired. The twist is that you can fulfill an order request partially if you don't have enough items, but it still counts as fulfilled as long as there is at least one item from that category available.

For each order, if there is any available inventory in the requested category (i.e. a positive count), you will count the order as fulfilled and then reduce the inventory for that category by the demanded quantity if possible, or set it to zero if the available items are fewer than requested.

The goal is to determine the maximum number of order requests that can be fulfilled (either fully or partially) when processed in the given order.

Note: Even if an order is not completely fulfilled because of insufficient inventory, it is still considered fulfilled as long as at least one item (i.e. inventory > 0) was available at the time of processing that order.

inputFormat

The input is given via standard input as follows:

• The first line contains two integers M and Q, where M is the number of items in the inventory and Q is the number of different product categories.
• The second line contains M integers, each representing the product category of an item. If M is 0, this line will be empty.
• The third line contains a single integer R, the number of order requests.
• The following R lines each contain two integers: the first is the product category requested and the second is the quantity requested.

outputFormat

Output a single integer on a new line, representing the total number of orders that can be fulfilled (either fully or partially) according to the rules described.

10 3
1 2 1 3 2 1 3 2 1 1
4
1 3
2 2
3 1
1 5

4