注意

yukicoder contest 279 (Zelkova and Cherry) の問題は 難易度順に並んではいない. よって, 問題文や難易度を表すの星の数, 正解者数等といった公開されている情報から問題を取捨選択することを強く推奨する.

お知らせ

判定結果のなかに, QLE が含まれている場合, 想定解またはジャッジコードに誤りが含まれいている可能性が大きいので, すぐに報告してください.

問題文

$N$ 種類の音 $1,\dots,N$ について, 音 $i$ を鳴らすと,音の得点として $A_i$を得る. また, 2つ以上の音を同時に鳴らすと, その音の得点の総和を得るが, その得点に加え, 音 $i, j$ を同時に鳴らしていたとき, そしてそのときに限り, 得点として更に $B_{i,j}$ だけ得る ($B_{i,j} < 0$ の場合もあり得る). $N$ 種類の音から1個以上の任意個の音を同時に鳴らしたとき, 得点の最大値とそれを達成する音の鳴らし方を求めよ.

制約

• $1 \leq N \leq 18$
• $0 \leq A_i \leq 10^9$
• $-10^9 \leq B_{i,j} \leq 10^9$
• $B_{i,i}=0\ (i=1,\dots,N)$
• $B_{i,j}=B_{j,i}\ (i,j=1,\dots,N)$
• 入力は全て整数である.

入力

$N$
$A_1\ \dots\ A_N$
$B_{1,1}\ \dots \ B_{1,N}$
$\vdots$
$B_{N,1}\ \dots \ B_{N,N}$

出力

$K (\geq 1)$ 種類の音 $j_1,\dots,j_K$ を鳴らした時に得点が最大値であり, その得点が $W$ であるとき, 以下のように出力せよ.

$W$
$j_1\ \dots j_K$

ただし, $j_1,\dots,j_K$ のなかに同じ音の番号を2つ以上含んでいてはいけない. また, 得点を最大にする音の鳴らし方が複数ある場合, どれを出力しても構わない. そして, 最後に改行することを忘れないこと. (2021/01/22 23:04 数字 $\to$ 音の番号に訂正)

サンプル

2
2 3
0 -4
-4 0

3
2

3
10 20 30
0 -2 3
-2 0 -5
3 -5 0

56
1 2 3

4
1 1 1 1
0 -10 -10 -10
-10 0 -10 -10
-10 -10 0 -10
-10 -10 -10 0

1
1