AT_past201912_g 組分け

[problemUrl]: https://atcoder.jp/contests/past201912-open/tasks/past201912_g あなたは、$ N $ 人の社員、社員 $ 1,\ \ldots,\ N $ を $ 3 $ つ以下のグループに最適に分割するプログラムを作ろうとしている。 すでに、社員のペア $ i,\ j $ $ (1\ \leqq\ i\

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

グループ分けの好ましさの最大値を出力せよ。

### 注意 この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 2\ \leqq\ N\ \leqq\ 10 $ - $ -1,000,000\ \leqq\ A_{i,j}\ \leqq\ 1,000,000 $ - 入力中の値はすべて整数である。 ### Sample Explanation 1 社員 $ 1,2,3 $ からなるグループ、社員 $ 4,5 $ からなるグループ、社員 $ 6 $ からなるグループの $ 3 $ つのグループを作ることを考える。このとき、同じグループに含まれる社員のペアは $ (1,2),\ (1,3),\ (2,3),\ (4,5) $ の $ 4 $ つ存在し、このグループ分けの好ましさは $ A_{1,2}\ +\ A_{1,3}\ +\ A_{2,3}\ +\ A_{4,5}\ =\ 10\ +\ 10\ +\ 10\ +\ 10\ =\ 40 $ となる。これが最適なグループ分けである。 ### Sample Explanation 2 全員を同じグループに含めても構わない。