题目背景

环

题目描述

给定无重边无自环的有向图 $G$ 和序列 $\{a_n\}$，每次可以花费 $a_i+a_j$ 的代价加上一条 $i\to j$ 的边，试花费最小代价使得可以找到 $k\geq 2$ 个不同的点 $p_1,p_2,\dots,p_k$，满足 $\forall i\in [1,k]$，都有一条 $p_i\to p_{i\bmod k+1}$ 的边。

输入格式

第一行两个整数 $n,m$（$2\le n\le 5 \times 10^5$，$n-1 \le m \le 10^6$），表示图的点数和边数。

第二行输入 $n$ 个整数，表示序列 $\{a_n\}$（$1\le a_i\le 10^9$）。

接下来 $m$ 行，每行两个整数 $u,v$（$1\le u,v\le n$），表示存在一条有向边 $u\to v$。

输出格式

一行一个整数表示最小代价。

5 5
1 2 3 4 5 
1 2
2 3
3 4
1 5
5 4 

3