QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB

# 3745. 排列

Statistics

Bobo 有一个长度为 $n$ 的数列 $p_1, p_2, \dots, p_n$ 和 $m$ 个二元组 $(a_1, b_1), (a_2, b_2), \dots, (a_m, b_m)$. 他想重新排列数列 $p$,使得 $\sum_{i = 1}^m |p_{a_i} - p_{b_i}|$ 最小。求最小值。

输入格式

输入文件包含多组数据,请处理到文件结束。

每组数据的第一行包含 $2$ 个整数 $n$ 和 $m$。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$.

最后 $m$ 行的第 $i$ 行包含 $2$ 个整数 $a_i$ 和 $b_i$.

输出格式

对于每组数据输出 $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 \leq n \leq 20$
  • $0 \leq m \leq \frac{n(n - 1)}{2}$
  • $0 \leq p_i \leq 10^9$
  • $1 \leq a_i < b_i \leq n$
  • 对于 $i \neq j$,$(a_i, b_i) \neq (a_j, b_j)$.
  • 数据组数不超过 $5,000$,且只有 $1$ 组数据的 $n > 10$.