There are $n$ children in a kindergarten who intend to decide whether or not to take a nap by voting. For them, this issue is not very important, so they decide to demonstrate a spirit of concession. Although everyone has their own opinion, they may cast a vote contrary to their original intention to accommodate the thoughts of their friends. We define the number of conflicts in a vote as the total number of conflicts between friends plus the number of people who vote contrary to their original intentions.

Our problem is: how should each child vote to minimize the total number of conflicts?

Input

The first line of the file contains two integers $n$ and $m$, where $2 \le n \le 300$ and $1 \le m \le n(n-1)/2$. Here, $n$ represents the total number of children, and $m$ represents the number of pairs of friends. The second line of the file contains $n$ integers, where the $i$-th integer represents the original intention of the $i$-th child; $1$ indicates they agree to nap, and $0$ indicates they oppose napping. The following $m$ lines each contain two integers $i, j$, representing that $i$ and $j$ are a pair of friends. We guarantee that no pair $i, j$ will be repeated.

Output

Output a single integer, which is the minimum possible number of conflicts.

Examples

Input 1

3 3
1 0 0
1 2
1 3
3 2

Output 1

1

Input 2

6 6
1 1 1 0 0 0
1 2
2 3
4 2
3 5
5 6

Output 2

2

Note

(In the first example, the optimal solution is obtained if all children vote in favor; in the second example, the optimal solution is obtained if all children vote contrary to their original intentions.)