Note

The problems of yukicoder contest 279 (Zelkova and Cherry) are not sorted in order of difficulty. Therefore, we strongly recommend choosing which problems to attempt based on publicly available information such as the problem statements, the number of stars indicating difficulty, and the number of solvers.

Announcement

If the judge results include QLE, it is very likely that the intended solution or the judge code contains an error, so please report it immediately.

Problem Statement

There are $N$ kinds of sounds $1,\dots,N$. Playing sound $i$ gives $A_i$ as the score of that sound. When two or more sounds are played simultaneously, you get the sum of the scores of those sounds; in addition to that score, if and only if sounds $i, j$ are being played simultaneously, you get a further $B_{i,j}$ points ($B_{i,j} < 0$ is possible). When any number (at least one) of the $N$ kinds of sounds are played simultaneously, find the maximum score and a way of playing sounds that achieves it.

Constraints

• $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)$
• All inputs are integers.

Input

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

Output

If the score is maximized by playing $K (\geq 1)$ kinds of sounds $j_1,\dots,j_K$, and that score is $W$, output as follows.

$W$
$j_1\ \dots j_K$

Here, $j_1,\dots,j_K$ must not contain the same sound number two or more times. If there are multiple ways of playing sounds that maximize the score, you may output any of them. Also, do not forget to print a newline at the end. (2021/01/22 23:04 Corrected "number" $\to$ "sound number")

Sample

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