在末日之后，Malnar 先生领导的新文明崛起了。他要做的第一件事就是重建帝国主干道上的电车网络。

沿街道有 $n$ 个潜在的站点位置，Malnar 先生将选择其中一些位置来建造电车站。由于第一处和第 $n$ 处位置必须作为终点站，因此这两个位置必须被选中。

对于每个位置，已知其参数 $x_i$ 和 $c_i$，其中 $x_i$ 表示该位置距离街道起点的距离，$c_i$ 表示在该位置建造车站时居民的不满度。有些车站附近有总是兜售昂贵车票的售货亭，而有些则有很棒的面包店。

共有 $m$ 名居民将使用这条规划中的线路，Malnar 先生决定询问他们每个人的意见。他了解到第 $i$ 位居民讨厌长度为 $d_i$ 的行程，并按以下方式评估车站的选择：

• 该居民的总满意度等于每对相邻选中车站的满意度之和。
• 对于距离为 $d$ 的两相邻选中车站，其满意度为 $|d - d_i|$。

Malnar 先生计算总满意度的方法是：将所有 $m$ 名居民的满意度相加，最后减去所有被选中车站 $k$ 的不满度 $c_k$。请输出 Malnar 先生在最优选择下能达到的最大总满意度。

输入格式

第一行包含两个自然数 $n$ ($2 \le n \le 100\,000$) 和 $m$ ($1 \le m \le 100\,000$)。

接下来一行包含 $m$ 个整数 $d_i$ ($0 \le d_i \le 10^7$)。

接下来 $n$ 行描述潜在的站点。每个站点由位置 $x_i$ ($0 \le x_i \le 10^7$) 和不满度 $c_i$ ($0 \le |c_i| \le 10^{12}$) 描述。$x_i$ 和 $c_i$ 均为整数，且满足 $x_1 < x_2 < \dots < x_n$。

输出格式

在唯一的一行中输出最大可能的满意度。

样例

输入 1

2 1
10
0 5
20 3

输出 1

2

输入 2

3 3
3 7 10
2 20
5 4
10 -3

输出 2

-1

输入 3

9 5
30 64 2 93 67
0 81
1 256
6 251
13 256
23 180
52 256
72 94
77 256
97 12

输出 3

137

说明 3

最优选择是站点 1, 3, 5, 7 和 9。此时相邻站点的距离分别为 6, 17, 49 和 25，居民的满意度分别为 61, 159, 89, 275 和 171。他们的满意度之和为 755，总不满度为 618，因此最终结果为 137。