22693_BallsAgain

Yes, balls again! Given n different color balls with points marked on them and m different columniform bottles. Each bottle has limited capacity to hold in balls. Now the job is to put the balls into the bottles. As his name, Max wants to know the maximum number of balls that can be put into bottles and meanwhile maximize the sum of points of the balls inside bottles.

Input contains multiple test data sets.

For each data set, first comes two integers n, m ( 1 ≤ n, m ≤ 200 ) in one line. Then n lines follow with one integer p ( 1 ≤ p ≤ 10⁶ ), the point of corresponding ball, per each line. Then follows m lines. Each has two integers c and q ( 0 ≤ c ≤ 200, 1 ≤ q ≤ 10⁶ ), the capacity of corresponding bottle (that is the maximum number of balls that bottle can hold) and the upper limit of point in the bottle (this means that all balls in this bottle should not have point larger than q). Input is terminated by EOF.

For each test data set, one output data set should be generated as follow:

Generates two integers in one line: B, the maximum number of balls filled into bottles. And S, the maximum sum of points of that B balls which are inside bottles.

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

1 2
2 9