← 返回题目列表

AtCoder · icpc2015summer_day4_c

C. 库鲁库鲁寿司

中文机器翻译题面 查看原题

问题陈述

Zephir 是“kuru kuru 寿司”餐厅的老板。在这些餐厅中,寿司被放置在旋转的环形传送带上并交付给顾客。

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

第 $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$。您可以假设 $s_i \neq t_i$ 对于任何 $0 \leq i \leq q-1$,并且 $s_i \neq s_j$ 或 $t_i \neq t_j$ 如果 $i \neq 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 的输出

6

示例输入 2

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

样本输入 2 的输出

32