AT_abc412_g [ABC412G] Degree Harmony

頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点 $ M $ 辺の単純無向グラフ $ G $ が与えられます。 $ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結ぶ辺です。 $ G $ の全域部分グラフ $ G' $ であって次の条件を満たすものを **良いグラフ** と呼びます。 - $ 1 \leq i \leq N $ を満たす全ての整数 $ i $ について次の条件が成り立つ。 - $ d_i $ を $ G' $ における頂点 $ i $ の次数とする。このとき $ d_i \leq A_i $ かつ $ d_i \bmod 2 = A_i \bmod 2 $ が成り立つ。 良いグラフが存在するか判定してください。存在する場合は、良いグラフとしてあり得るグラフのうち辺数が最小のものの辺数を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_M $ $ v_M $

良いグラフが存在しない場合は `-1` を出力せよ。存在する場合は、良いグラフとしてあり得るグラフのうち辺数が最小のものの辺数を出力せよ。

### Sample Explanation 1 辺集合が $ 2 $ 番目の辺のみで構成された全域部分グラフは良いグラフです。 ### Constraints - $ 1 \leq N \leq 150 $ - $ 0 \leq M \leq \frac{N(N-1)}{2} $ - $ 1 \leq u_i \lt v_i \leq N $ - 与えられるグラフは単純 - $ 1 \leq A_i \leq 150 $ - $ 1 \leq \sum_{i=1}^N A_i \leq 150 $ - 入力される値は全て整数