Fleeland 火山岛从未有过完善的电网，但最终，生物质替代能源集团 (BAPC) 同意为该岛建设发电厂和电网。

岛上的海岸边有 $n$ 座城市。BAPC 对这些城市进行了勘测，并提出了 $m$ 个可能的发电厂选址，第 $i$ 个方案指出公司可以在城市 $c_i$ 建造发电厂，成本为 $a_i$。

这些发电厂非常先进，单座发电厂即可为整个岛屿供电，但火山的存在使得在岛上架设输电线变得非常危险。对于 $1 \le i < n$，公司可以在城市 $i$ 和 $i+1$ 之间架设输电线，成本为 $b_i$，而在城市 $n$ 和 $1$ 之间架设输电线的成本为 $b_n$。如果一座城市拥有发电厂，或者通过输电线与拥有发电厂的城市相连，那么它就能获得电力。

请问为岛上所有城市供电的最廉价方式是什么？

CC BY-SA 2.0 By Oran Viriyincy on Flickr

输入格式

输入包含：

• 第一行包含两个整数 $n$ ($3 \le n \le 10^5$) 和 $m$ ($1 \le m \le n$)，分别表示城市数量和可能的发电厂选址数量。
• 接下来 $m$ 行，第 $i$ 行包含 $c_i$ ($1 \le c_i \le n$) 和 $a_i$ ($1 \le a_i \le 10^9$)，表示第 $i$ 个可能的发电厂选址及其建造费用。
• 最后一行包含 $n$ 个整数 $b_i$ ($1 \le b_i \le 10^9$)，表示架设输电线的费用。

$c_1, \dots, c_m$ 的值是唯一的，并按严格递增顺序给出。

输出格式

输出为岛上所有城市供电的最小成本。

样例

样例输入 1

3 2
1 100
2 200
150 300 150

样例输出 1

400

样例输入 2

3 2
1 100
2 200
300 300 150

样例输出 2

450