4572 - 安排顾客

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

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

输入

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

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

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

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

输出

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

样例

输入

3
10 50
2 100
5 30
3
4 6 9

输出

130

来源

信友队

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题