#BZOJ2465. 小球
-
ID: 915
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
小球
No submission language available for this problem.
题目描述
给定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
数据范围与约定
对于全部的数据，有1<=n<=200，0<=m<=200，1 <= p <= 10^6, 0 <= c <= 200, 1 <= q <= 10^6.