AT_abc412_g [ABC412G] Degree Harmony

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.

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 $

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

### Sample Explanation 1 The spanning subgraph whose edge set consists of only the $ 2 $ nd edge is a good graph. ### 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.