Background

Special for beginners, ^_^

Description

某群岛有n个岛屿，岛屿之间有桥相连，所有的桥恰好组成一个环。可以按照顺时针方向，给每个岛屿编号，即岛1和岛2相连，岛2和岛3相连，岛n和岛1相连。可选择其中m个岛屿建设发电厂，岛屿ci建设的代价是ai。这些都是现代化的发电厂，一个电厂容量就足够给整个群岛供电。为了方便维护，输电线必须沿着路或者桥走，即岛屿i和岛屿i+1之间建设输电线的代价是bi，岛屿n和岛屿1之间建设输电线的代价是bn。某个岛通电的条件是或者该岛有发电厂或者该岛能通过输电线接入发电厂。问把所有这些岛都通电的最小总代价是多少？

Format

Input

输入第一行包含岛屿数量n（3 ≤ n ≤ 1e5）和可以建设发电厂的岛屿数量m（1 ≤ m ≤ n）。接下来m行，每行两个数ci（1 ≤ ci ≤ n）和ai（1 ≤ ai ≤ 1e9），表示在城市ci建设发电厂的代价为ai。接下来1行n个整数表示每个岛屿和它下一个岛屿之间架设输电线路的代价bi（1 ≤ bi ≤ 1e9）。

Output

输出所有岛屿通电的最小总代价。

Samples

3 2
1 100
2 200
150 300 150

400

Limitation

1s, 1024KiB for each test case.