13161번 - 분단의 슬픔 스페셜 저지

UCPC에는 N명의 사람이 있다. 먼 옛날 쇼킹핫치킨에 대한 논쟁에서 시작된 이념의 대립으로 UCPC에는 kriii를 따르는 쇼킹핫진보 진영 A와, august14를 따르는 쇼킹핫보수 진영 B의 두 진영이 존재한다. 모든 사람은 둘 중 한 진영에 소속되어 있으며, 두 진영에 동시에 들어가는 것은 불가능하다.

i번 사람과 j번 사람에 대해 서로 다른 진영에 들어가게 될 경우 슬픈 정도 w[i, j]가 주어진다. 일부 사람들은 쇼킹핫에 관한 자신의 철학이 강해 무조건 A진영에 들어가는 사람도 있고, 무조건 B진영에 들어가는 사람도 있다. 물론 치킨은 무엇이든 옳으므로 두 진영 어디에 가든 상관없는 사람도 있다.

N명의 사람들이 적절히 두 진영에 나누어 들어갈 때, 슬픔 정도의 합이 최소가 되게 하라.

첫 번째 줄에는 UCPC 구성원의 수 N(1 ≤ N ≤ 500)이 주어진다. 두 번째 줄에는 N개의 정수가 주어지는데, i번째 수가 1이면 i번 사람은 무조건 A진영에 들어가야 함을, 2라면 무조건 B진영에 들어가야 함을, 0이면 어느 진영에 들어가든지 상관 없다는 것을 의미한다.

세 번째 줄부터 N개의 줄에 걸쳐 i번 사람과 j번 사람이 다른 진영에 들어갈 때의 슬픔 정도 w[i, j]가 주어진다. (i+2)번째 줄에 j번째 수는 w[i, j]를 의미한다. 주어지는 입력은 항상 w[i, j]=w[j, i]를 만족하고, w[i, i]=0이다. w[i, j]는 1,000보다 크지 않은 음이 아닌 정수이다.

첫 줄에 N명의 사람이 A, B 두 진영에 적절히 들어가 슬픈 정도의 합이 최소가 될 때의 슬픔 정도의 합을 출력한다. 두 번째 줄에는 슬픈 정도의 합이 최소가 될 때 A진영에 들어가는 사람들의 번호를 공백으로 구분하여 출력하고, 세 번째 줄에는 슬픈 정도의 합이 최소가 될 때 B진영에 들어가는 사람들의 번호를 공백으로 구분하여 출력한다. 만약 한 진영에 사람이 한 명도 들어가지 않은 경우 빈 줄을 출력한다. 가능한 경우가 여러 가지인 경우 그중 아무거나 하나 출력한다.