P73205

安排顾客

难度 3 级 小学 算法入门 贪心
讨论 统计 2通过 3提交 66.7%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

有一家餐馆有k张桌子,第i张桌子最大可以坐下Ri 个人。现在来了n伙顾客,第i群顾客共有Ci个人,将会带来收益P。

每张桌子只能安排一群顾客,而且同一群顾客都要坐在一张桌子上。问接受哪几群顾客,并分别安排在哪几张桌子可以带来最大的收益。

输入

第一行包含一个整数n(1<=n<=50000)。

接下来有n行,每行有两个整数ci,pi 表示顾客的人数与收益的大小

接下来一行一个整数k(1<=k<=50000)。

最后一行包含k个整数r1 r2 ... rk 表示桌子能坐的人数

输出

输出一个数,表示最大的收益

样例

样例 1
输入
3
10 50
2 100
5 30
3
4 6 9
输出
130
Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交