该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

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

输入格式

在文件 axis.in 中读入。

第一行两个整数 $n, m$。

之后的 $n$ 行，每行两个数 $a_i, b_i$。

之后一行 $m$ 个数表示 $r_i$。

输出格式

在文件 axis.out 中输出。

一个数表示答案。

样例

样例输入 #1

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

样例输出 #1

44

数据范围

对于前 $20\%$ 的数据，$n, m \le 10$。

对于前 $40\%$ 的数据，$n, m, a_i, r_i \le 50$。

另有 $20\%$ 的数据，满足 $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$。