题目描述

有一个坐标轴，将从 $0$ 到 $n$ 的线段平均分成 $n$ 个区间，第 $i$ 个区间为 $(i-1, i]$。每个区间里有一个物品，第 $i$ 个区间中的物品体积为 $a_i$，价值为 $b_i$。

你有 $m$ 行动机会，第 $i$ 次会携带一个容量为 $r_i$ 的包。一次行动从原点出发，向右走过连续的一段后返回，或者在原点直接结束。走过一个区间时，可以选择将当前物品放入包内来获得这个物品，前提是物品体积不大于包的剩余容量。如果没有获得这个物品，则必须将这个物品摧毁。

包的容量单调不减，也就是说有 $r_{i-1} \le r_i$。

求 $m$ 次行动获得的物品的最大总价值。

输入格式

第一行两个整数 $n,m$。 之后的 $n$ 行，每行两个数 $a_i,b_i$。 之后一行 $m$ 个数表示 $r_i$。

输出格式

输出一个数表示答案。

样例输入 #1

5 3
2 10
2 5
1 22
3 7
6 8
1 3 7

样例输出 #1

44

数据范围

• 对于前部分数据，$n,m \le 10$
• 对于前部分数据，$n,m,a_i,r_i \le 50$
• 另有部分数据，满足 $m \le 200$
• 对于100%的数据：$1 \le n \le 200$，$1 \le m \le 10^5$，$1 \le a_i \le 200$，$1 \le b_i \le 10^5$，$1 \le r_i \le 200$