Problem Statement

You are given a simple undirected graph $G$ with $N$ vertices and $M$ edges, where vertices are numbered from $1$ to $N$. The $i$-th edge connects vertices $u_i$ and $v_i$. A spanning subgraph $G'$ of $G$ that satisfies the following condition is called a good graph:

• For all integers $i$ satisfying $1 \leq i \leq N$, the following condition holds:
• Let $d_i$ be the degree of vertex $i$ in $G'$. Then, $d_i \leq A_i$ and $d_i \bmod 2 = A_i \bmod 2$ hold.

Determine whether a good graph exists. If it exists, output the minimum number of edges among all possible good graphs.

Constraints

• $1 \leq N \leq 150$
• $0 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq u_i < v_i \leq N$
• The given graph is simple.
• $1 \leq A_i \leq 150$
• $1 \leq \sum_{i=1}^N A_i \leq 150$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 \dots A_N
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

If no good graph exists, output -1. If it exists, output the minimum number of edges among all possible good graphs.