AT_abc371_c [ABC371C] Make Isomorphic

[problemUrl]: https://atcoder.jp/contests/abc371/tasks/abc371_c 頂点 $ 1, $ 頂点 $ 2,\ldots, $ 頂点 $ N $ の $ N $ 個の頂点からなる単純無向グラフ $ G,H $ が与えられます。 $ G $ には $ M\ _\ G $ 本の辺があり、$ i $ 本目 $ (1\leq\ i\leq\ M\ _\ G) $ の辺は頂点 $ u\ _\ i $ と頂点 $ v\ _\ i $ を結んでいます。 $ H $ には $ M\ _\ H $ 本の辺があり、$ i $ 本目 $ (1\leq\ i\leq\ M\ _\ H) $ の辺は頂点 $ a\ _\ i $ と頂点 $ b\ _\ i $ を結んでいます。 あなたは、グラフ $ H $ に対して次の操作を $ 0 $ 回以上の好きな回数繰り返すことができます。 - $ 1\leq\ i\lt\ j\leq\ N $ を満たす整数の組 $ (i,j) $ をひとつ選ぶ。$ A\ _\ {i,j} $ 円を支払って、頂点 $ i $ と頂点 $ j $ を結ぶ辺がなければ追加し、あれば取り除く。 $ G $ と $ H $ を同型にするために少なくとも何円支払う必要があるか求めてください。 単純無向グラフとは？ **単純無向グラフ**とは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。 グラフの同型とは？ $ N $ 頂点のグラフ $ G $ と $ H $ が**同型**であるとは、ある $ (1,2,\ldots,N) $ の並べ替え $ (P\ _\ 1,P\ _\ 2,\ldots,P\ _\ N) $ が存在して、どの $ 1\leq\ i\lt\ j\leq\ N $ に対しても - $ G $ に頂点 $ i, $ 頂点 $ j $ を結ぶ辺が存在するとき、かつそのときに限り $ H $ に頂点 $ P\ _\ i, $ 頂点 $ P\ _\ j $ を結ぶ辺が存在する が成り立つことをいいます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M\ _\ G $ $ u\ _\ 1 $ $ v\ _\ 1 $ $ u\ _\ 2 $ $ v\ _\ 2 $ $ \vdots $ $ u\ _\ {M\ _\ G} $ $ v\ _\ {M\ _\ G} $ $ M\ _\ H $ $ a\ _\ 1 $ $ b\ _\ 1 $ $ a\ _\ 2 $ $ b\ _\ 2 $ $ \vdots $ $ a\ _\ {M\ _\ H} $ $ b\ _\ {M\ _\ H} $ $ A\ _\ {1,2} $ $ A\ _\ {1,3} $ $ \ldots $ $ A\ _\ {1,N} $ $ A\ _\ {2,3} $ $ \ldots $ $ A\ _\ {2,N} $ $ \vdots $ $ A\ _\ {N-1,N} $

答えを出力せよ。

### 制約 - $ 1\leq\ N\leq8 $ - $ 0\leq\ M\ _\ G\leq\dfrac{N(N-1)}2 $ - $ 0\leq\ M\ _\ H\leq\dfrac{N(N-1)}2 $ - $ 1\leq\ u\ _\ i\lt\ v\ _\ i\leq\ N\ (1\leq\ i\leq\ M\ _\ G) $ - $ (u\ _\ i,v\ _\ i)\neq(u\ _\ j,v\ _\ j)\ (1\leq\ i\lt\ j\leq\ M\ _\ G) $ - $ 1\leq\ a\ _\ i\lt\ b\ _\ i\leq\ N\ (1\leq\ i\leq\ M\ _\ H) $ - $ (a\ _\ i,b\ _\ i)\neq(a\ _\ j,b\ _\ j)\ (1\leq\ i\lt\ j\leq\ M\ _\ H) $ - $ 1\leq\ A\ _\ {i,j}\leq\ 10\ ^\ 6\ (1\leq\ i\lt\ j\leq\ N) $ - 入力はすべて整数 ### Sample Explanation 1 与えられたグラフはそれぞれ以下のようになります。 !\[\](https://img.atcoder.jp/abc371/fbdb304dc71eecd7ddec97276a9c7040.png) たとえば、$ H $ に対して次のような $ 4 $ つの操作を順に行うことで、$ 9 $ 円を支払って$ G $ と $ H $ を同型にすることができます。 - $ (i,j)=(1,3) $ として操作を行う。$ H $ には頂点 $ 1 $ と頂点 $ 3 $ を結ぶ辺があるので、$ 1 $ 円を支払ってこれを取り除く。 - $ (i,j)=(2,5) $ として操作を行う。$ H $ には頂点 $ 2 $ と頂点 $ 5 $ を結ぶ辺はないので、$ 2 $ 円を支払ってこれを追加する。 - $ (i,j)=(1,5) $ として操作を行う。$ H $ には頂点 $ 1 $ と頂点 $ 5 $ を結ぶ辺があるので、$ 1 $ 円を支払ってこれを取り除く。 - $ (i,j)=(3,5) $ として操作を行う。$ H $ には頂点 $ 3 $ と頂点 $ 5 $ を結ぶ辺はないので、$ 5 $ 円を支払ってこれを追加する。 操作の結果、$ H $ は以下のようになります。 !\[\](https://img.atcoder.jp/abc371/68a56da8ec89b769989ae7d07bf163cd.png) 支払う金額を $ 8 $ 円以下にして $ G $ と $ H $ を同型にすることはできないため、`9` を出力してください。 ### Sample Explanation 2 たとえば、$ (i,j)=(2,3),(2,4),(3,4) $ とした $ 3 $ 回の操作を行うことで $ G $ と $ H $ を同型にすることができます。 ### Sample Explanation 3 たとえば、$ (i,j)=(4,5) $ とした $ 1 $ 回の操作を行うことで $ G $ と $ H $ を同型にすることができます。 ### Sample Explanation 4 $ G $ や $ H $ には辺が含まれていないこともあります。 また、一度も操作をする必要がないこともあります。