Bobo 有一个长度为 n 的数列 p1,p2,…,pn 和 m 个二元组 (a1,b1),(a2,b2),…,(am,bm). 他想重新排列数列 p,使得 ∑mi=1|pai−pbi| 最小。求最小值。
输入格式
输入文件包含多组数据,请处理到文件结束。
每组数据的第一行包含 2 个整数 n 和 m。
第二行包含 n 个整数 p1,p2,…,pn.
最后 m 行的第 i 行包含 2 个整数 ai 和 bi.
输出格式
对于每组数据输出 1 个整数表示所求的最小值。
样例输入
3 2 1 2 5 1 2 2 3 3 3 1 2 5 1 2 1 3 2 3 20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
样例输出
4 8 0
数据范围
- 1≤n≤20
- 0≤m≤n(n−1)2
- 0≤pi≤109
- 1≤ai<bi≤n
- 对于 i≠j,(ai,bi)≠(aj,bj).
- 数据组数不超过 5,000,且只有 1 组数据的 n>10.