Kuru Kuru Sushi

Zephir is the owner of the kuru kuru sushi restaurants. In these restaurants, sushi is placed on a rotating circular belt conveyor and delivered to customers.

Zephir owns $n$ restaurants numbered from 0 to $n-1$. The restaurants are placed on the circumference of a circle, and a large belt conveyor runs underground between each pair of adjacent restaurants. One day, some restaurants ran short of sushi ingredients, so he decided to transport ingredient foods between restaurants using these conveyors.

The $i$-th ($0 \leq i \leq n-2$) belt conveyor connects restaurants $i$ and $i+1$. The $(n-1)$-th belt conveyor connects restaurants $n-1$ and $0$. The length of the $i$-th conveyor is $w_i$. He wants to transport $q$ foods, where the $i$-th food is transported from restaurant $s_i$ to restaurant $t_i$.

Each conveyor can transport food in only one direction, and Zephir can choose that direction. The directions cannot change while all $q$ foods are being transported. The transportation cost of the $i$-th food is the sum of the lengths of the conveyors on the shortest path from $s_i$ to $t_i$. Zephir must set the direction of every conveyor so that all foods can be transported. Calculate the minimum total cost, which is the sum of the transportation costs of all $q$ foods.

The first line contains two integers $n$ and $q$. Here $n$ ($3 \leq n \leq 10^5$) is the number of restaurants, and $q$ ($1 \leq q \leq 10^5$) is the number of foods. The next line contains $n$ integers $w_i$ ($1 \leq w_i \leq 10^5$). Each of the following $q$ lines contains two integers $s_i$ and $t_i$ ($0 \leq s_i, t_i \leq n-1$). It is guaranteed that $s_i \neq t_i$ for every $i$, and that $s_i \neq s_j$ or $t_i \neq t_j$ for every pair $i \neq j$.

$n$ $q$

$w_0$ $w_1$ ... $w_{n-1}$

$s_0$ $t_0$

...

$s_{q-1}$ $t_{q-1}$

Print the minimum total cost of the food transportation. If it is impossible to transport all foods to their destinations, print -1.