The Sadness of Division

A club has $N$ members. An old argument has split the club into camp A and camp B. Every member belongs to exactly one camp, and nobody belongs to both.

If member $i$ and member $j$ belong to different camps, that pair creates sadness $w[i][j]$. Some members hold their position so firmly that they must join camp A, and some must join camp B. Others do not care which camp they join.

Divide the $N$ members between the two camps so that the total sadness is minimal.

The first line contains the number of members $N$ ($1 \le N \le 500$).

The second line contains $N$ integers. If the $i$-th number is 1, member $i$ must join camp A; if it is 2, member $i$ must join camp B; if it is 0, member $i$ may join either camp.

Each of the next $N$ lines contains $N$ integers. The $j$-th number on line $i+2$ is $w[i][j]$. The input always satisfies $w[i][j] = w[j][i]$ and $w[i][i] = 0$, and every $w[i][j]$ is a non-negative integer no larger than 1000.

Print the minimum total sadness on the first line.

On the second line print the numbers of the members in camp A in increasing order, separated by single spaces. On the third line print the numbers of the members in camp B the same way. If a camp holds nobody, print an empty line for it.

Several divisions can reach the minimum total sadness, so only one of them counts as correct. Put a member in camp A only if that member belongs to camp A in every division that reaches the minimum, and put everyone else in camp B. The division built this way also reaches the minimum total sadness, and its camp A is contained in the camp A of every other minimal division, so exactly one division satisfies the rule.