You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

收菜

题目描述

台风就要来啦，WFYZ的小菜园需要抢收菜品。WFYZ小菜园有 $N$ 个可以收获的蔬菜，每个蔬菜有质量 $M_i$ 和价值 $V_i$。

你有 $K$ 个袋子，每袋可容纳的最大质量为 $C_i$。每个袋子仅能放一种蔬菜，问你可以收获蔬菜的最大价值和是多少？

输入格式

第一行包含两个正整数 $N$ 和 $K$。

接下来 $N$ 行中的每行包含两个正整数 $M_i$ 和 $V_i$。

接下来 $K$ 行中的每行包含一个正整数 $C_i$。

输出格式

输出一行，收获蔬菜的最大价值和。

样例 #1

样例输入 #1

2 1
5 10
100 100
11

样例输出 #1

10

样例 #2

样例输入 #2

3 2
1 65
5 23
2 99
10
2

样例输出 #2

164

提示

【数据规模与约定】

对于$60\%$的数据范围 $1\le N,K\le 10000$

对于$100\%$的数据范围 $1\le N,K\le 3\times 10^5$， $1\le M_i,V_i\le 10^6$， $1\le C_i\le 10^8$。

样例 2 解释

将第一件物品放在第二袋中，将第三件物品放在第一袋中。