AT_abc318_d [ABC318D] General Weighted Max Matching

[problemUrl]: https://atcoder.jp/contests/abc318/tasks/abc318_d 頂点に $ 1 $ から $ N $ の番号が付いた $ N $ 頂点の重み付き無向完全グラフが与えられます。頂点 $ i $ と頂点 $ j\ (i\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ D_{1,2} $ $ D_{1,3} $ $ \ldots $ $ D_{1,N} $ $ D_{2,3} $ $ \ldots $ $ D_{2,N} $ $ \vdots $ $ D_{N-1,N} $

答えを整数として出力せよ。

### 制約 - $ 2\leq\ N\leq\ 16 $ - $ 1\leq\ D_{i,j}\ \leq\ 10^9 $ - 入力される数値は全て整数 ### Sample Explanation 1 頂点 $ 1 $ と頂点 $ 3 $ を結ぶ辺、頂点 $ 2 $ と頂点 $ 4 $ を結ぶ辺を選ぶと、辺の重みの総和が $ 5+8=13 $ となります。 これが達成可能な最大値であることが示せます。 ### Sample Explanation 2 $ N $ が奇数の場合もあります。