题目描述

Zephir是“kuru kuru sushi”餐厅的老板。在这些餐厅中，寿司放置在一个旋转的圆形传送带上并送到顾客手中。

Zephir拥有编号为0到n-1的n个餐厅。由于他对旋转的热情，这些餐厅位于一个圆的周长上，并且相邻餐厅之间有着巨大的地下传送带。一天，某些餐厅的寿司材料不足。因此，他决定使用这些传送带在餐厅之间运输一些原料食品。

第i条（$0\leq i\leq 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$
$w_0$ $w_1$ ... $w_{n-1}$
$s_0$ $t_0$
...
$s_{q-1}$ $t_{q-1}$

第一行包含两个整数$n$和$q$。$n$（$3 \leq n \leq 10^5$）表示餐厅的数量，$q$（$1 \leq q \leq 10^5$）表示要运输的食物的数量。接下来的一行包含$n$个整数。$w_i$（$1 \leq w_i \leq 10^5$）表示第i条传送带的长度。以下$q$行中的每一行都包含两个整数$s_i$（$0 \leq s_i \leq n-1$）和$t_i$（$0 \leq t_i \leq n-1$）。它们分别表示第i种食物应从餐厅$s_i$运送到$t_i$。可以假设对于任何$0 \leq i \leq q-1$，$s_i \neq t_i$，并且如果$i \neq j$，则$s_i \neq s_j$或$t_i \neq t_j$（其中$0 \leq i, j \leq q-1$）。

输出

打印食物运输的最小总成本。如果无法将所有食物运送到每个目的地，请打印-1。

样例输入 1

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

### 样例输出 1

```plain
6```

* * *

### 样例输入 2

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

### 样例输出 2

```plain
32```

* * *