쿠루쿠루 스시

제퍼는 쿠루쿠루 스시 식당의 주인이다. 이 식당들에서는 스시를 회전하는 원형 벨트 컨베이어에 올려 손님에게 전달한다.

제퍼는 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$로 옮겨진다.

각 컨베이어는 한 방향으로만 음식을 옮길 수 있고, 그 방향은 제퍼가 정할 수 있다. 모든 $q$개의 음식을 옮기는 동안에는 방향을 바꿀 수 없다. $i$번째 음식의 운송 비용은 $s_i$에서 $t_i$까지 최단 경로에 있는 컨베이어 길이의 합이다. 제퍼는 모든 음식을 운반할 수 있도록 각 컨베이어의 방향을 정해야 한다. 모든 음식의 운송 비용 합의 최솟값을 구하라.

첫째 줄에 두 정수 $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$)가 주어진다. 이어지는 $q$개의 줄에는 두 정수 $s_i$와 $t_i$($0 \leq s_i, t_i \leq n-1$)가 주어진다. 모든 $i$에 대해 $s_i \neq t_i$이며, $i \neq j$이면 $s_i \neq s_j$ 또는 $t_i \neq t_j$이다.

$n$ $q$

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

$s_0$ $t_0$

...

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

모든 음식을 목적지로 옮길 수 없으면 -1을 출력한다. 그렇지 않으면 음식 운송 비용 합의 최솟값을 출력한다.