[中山市选2009]小球

给定 $n$ 个不同颜色的球，每个球都有一个分数，同时有 $m$ 个瓶子，每个瓶子都有固定的容量。现在，你必须把球放到瓶子里面。请编程计算最多能放多少个球到这些瓶子里。

输入格式

输入包含多组数据。

每组数据的第一行为两个整数 $n, m$，分别表示球的个数和瓶子的个数。

接下来的 $n$ 行，每一行包含一个整数 $p$，表示相应的球的分数。

接下来的 $m$ 行，每一行包含两个整数 $c$ 和 $q$，分别表示这个瓶子的容量（最多能装多少个球）和分数上界（放进该瓶子的每个球的分数都不能超过 $q$）。

当输入的 $n$、$m$ 均为 $0$ 时，表示输入结束。

输出格式

对于每组数据，输出两个整数 $B$ 和 $S$，分别表示总共能放进瓶子里的球的最大数目，以及在这个前提下，放进瓶子里面的所有球的最大分数总和。$B$ 和 $S$ 以空格隔开，每组答案独占一行。

样例输入

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

样例输出

1 2
2 9

样例解释

第一组有两个球，分数分别为 $2$ 和 $3$；唯一的瓶子容量为 $1$、分数上界为 $2$，只能装下分数为 $2$ 的球，所以答案是 1 2。

第二组两个球的分数为 $4$ 和 $5$，两个瓶子的容量与分数上界分别为 $(2,4)$ 和 $(2,5)$：把分数 $4$ 的球放进第一个瓶子、分数 $5$ 的球放进第二个瓶子，两个球都能放下，总分为 $4+5=9$，所以答案是 2 9。

数据范围

对于全部的数据：

• $1\le n\le 200$；
• $0\le m\le 200$；
• $1\le p\le 10^6$；
• $0\le c\le 200$；
• $1\le q\le 10^6$。

来源与许可

本题为中山市选 2009 试题「小球」，题面与测试数据整理自 BZOJ 2465。

样例 1

输入

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

输出

1 2
2 9