Bobo has a sequence $p_1, p_2, \dots, p_n$ of length $n$ and $m$ pairs $(a_1, b_1), (a_2, b_2), \dots, (a_m, b_m)$. He wants to rearrange the sequence $p$ such that $\sum_{i = 1}^m |p_{a_i} - p_{b_i}|$ is minimized. Find the minimum value.

The input contains multiple test cases. Process until the end of the file.

Each test case starts with a line containing two integers $n$ and $m$.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$.

Each of the next $m$ lines contains two integers $a_i$ and $b_i$.

For each test case, output one integer representing the minimum value.

Constraints

• $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$
• For $i \neq j$, $(a_i, b_i) \neq (a_j, b_j)$.
• The number of test cases does not exceed $5,000$, and there is at most $1$ test case with $n > 10$.

Examples

Input 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

Output 1

4
8
0