Description

Bobo 有一个长度为 n 的数列 p₁, p₂, …, p_n 和 m 个二元组 (a₁, b₁), (a₂, b₂), …, (a_m, b_m). 他想重新排列数列 p，使得 $\sum_{i = 1}^m |p_{a_i} - p_{b_i}|$ 最小。求最小值。

• 1 ≤ n ≤ 20
• $0 \leq m \leq \frac{n(n - 1)}{2}$
• 0 ≤ p_i ≤ 10⁹
• 1 ≤ a_i < b_i ≤ n
• 对于 i ≠ j，(a_i, b_i) ≠ (a_j, b_j).
• 数据组数不超过 5, 000，且只有 1 组数据的 n > 10.

Input

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

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

第二行包含 n 个整数 p₁, p₂, …, p_n.

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

Output

对于每组数据输出 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