분단의 슬픔

어느 모임에 $N$명이 있다. 오래된 논쟁 때문에 모임은 A진영과 B진영으로 갈라졌다. 모든 사람은 두 진영 중 정확히 한 곳에 속하고, 두 곳에 동시에 속할 수는 없다.

$i$번 사람과 $j$번 사람이 서로 다른 진영에 속하면 슬픔 $w[i][j]$가 생긴다. 신념이 확고해서 반드시 A진영에 들어가야 하는 사람이 있고, 반드시 B진영에 들어가야 하는 사람도 있다. 어느 진영이든 상관없는 사람도 있다.

$N$명을 두 진영으로 나눌 때 슬픔의 합을 최소로 만들어라.

첫째 줄에 사람 수 $N$($1 \le N \le 500$)이 주어진다.

둘째 줄에 $N$개의 정수가 주어진다. $i$번째 수가 1이면 $i$번 사람은 반드시 A진영에 들어가야 하고, 2이면 반드시 B진영에 들어가야 하며, 0이면 어느 진영에 들어가도 된다.

셋째 줄부터 $N$개의 줄에 각각 $N$개의 정수가 주어진다. $(i+2)$번째 줄의 $j$번째 수가 $w[i][j]$이다. 입력은 항상 $w[i][j] = w[j][i]$와 $w[i][i] = 0$을 만족하고, $w[i][j]$는 1000 이하의 음이 아닌 정수이다.

첫째 줄에 슬픔의 합의 최솟값을 출력한다.

둘째 줄에 A진영에 들어가는 사람의 번호를 증가하는 순서로 공백 하나씩 두고 출력하고, 셋째 줄에 B진영에 들어가는 사람의 번호를 같은 방식으로 출력한다. 한 진영에 사람이 없으면 그 줄은 빈 줄로 출력한다.

슬픔의 합이 최소인 나누기는 여러 가지일 수 있으므로 그중 하나만 정답으로 인정한다. 슬픔의 합이 최소인 모든 나누기에서 A진영에 속하는 사람만 A진영에 넣고, 나머지 전부를 B진영에 넣어라. 이렇게 만든 나누기도 슬픔의 합이 최소이고, A진영이 다른 모든 최소 나누기의 A진영에 포함되므로 이 조건을 만족하는 나누기는 하나뿐이다.