Migrated from Lutece 737 最小代价

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定$n$个点权值依次为$w_i$（$1\le i\le n$）对于一个图使得所有点连通中其中每个点的度数依次为$d_i$（$1\le i\le n$）那么这个图的代价为$\sum_{i=1}^{n}d_i\times w_i$，求使得所有点连通的最小代价

Input

包含多组数据，对于每组数据第一行为两个正整数$n$（$n\le 10000$），$m$($m\le 100000$)分别表示点数和可以用于连接的边数。接下来的一行包含$n$个数，表示每个点的权值$w\_i$（$w\_i\le 1000$）

Output

每组数据仅包含一个正整数，即最小代价，若无法使图连通输出$-1$

Samples

3 3
1 2 3
1 2
2 3
3 1

7

Resources

2013 UESTC ACM Training for Graph Theory