Zephir 拥有一家“回转寿司”餐厅。在这些餐厅中，寿司被放置在旋转的环形传送带上，并送达给顾客。

Zephir 拥有 $n$ 家餐厅，编号从 $0$ 到 $n-1$。由于他对旋转的热爱，这些餐厅被放置在一个圆周上，并且在相邻的餐厅之间有巨大的地下传送带。有一天，一些餐厅的寿司食材短缺。因此，他决定利用这些传送带在餐厅之间运输一些食材。

第 $i$ 条（$0 \le i \le n-2$）传送带连接餐厅 $i$ 和 $i+1$。第 $n-1$ 条传送带连接餐厅 $n-1$ 和 $0$。第 $i$ 条传送带的长度为 $w_i$。他想要运输 $q$ 份食材，从某些餐厅运往其他餐厅。第 $i$ 份食材应从餐厅 $s_i$ 运输到 $t_i$。

Zephir 想要最小化总运输成本。每份食材的运输成本可以通过设置传送带的方向来改变。每条传送带只能向一个方向运输食材，该方向由 Zephir 设置。此外，在运输所有 $q$ 份食材的过程中，传送带的设置不能更改。第 $i$ 份食材的运输成本是餐厅 $s_i$ 到 $t_i$ 最短路径上所有传送带长度之和。他必须设置传送带的方向以运输所有食材。编写一个程序，计算总运输成本（即所有 $q$ 份食材运输成本之和）的最小值。

输入格式

第一行包含两个整数 $n$ 和 $q$。$n$ ($3 \le n \le 10^5$) 表示餐厅的数量，$q$ ($1 \le q \le 10^5$) 表示需要运输的食材数量。下一行包含 $n$ 个整数，$w_i$ ($1 \le w_i \le 10^5$) 表示第 $i$ 条传送带的长度。接下来的 $q$ 行，每行包含两个整数 $s_i$ ($0 \le s_i \le n-1$) 和 $t_i$ ($0 \le t_i \le n-1$)，表示第 $i$ 份食材应从餐厅 $s_i$ 运输到 $t_i$。你可以假设对于任何 $0 \le i \le q-1$，$s_i \neq t_i$，且对于任何 $0 \le i, j \le q-1$，$s_i \neq s_j$ 或 $t_i \neq t_j$（若 $i \neq j$）。

输出格式

输出总运输成本的最小值。如果无法将所有食材运送到各自的目的地，则输出 $-1$。

样例

样例输入 1

4 4
1 1 1 1
0 1
0 3
2 3
3 0

样例输出 1

6

样例输入 2

5 3
4 5 6 7 8
0 1
0 3
4 2

样例输出 2

32