마피아

은진이는 마피아 게임에서 자신이 마지막으로 남은 마피아라는 사실을 알게 되었다. 나머지 참가자는 모두 시민이며, 참가자 번호는 0번부터 N-1번까지이다.

게임은 생존자 수에 따라 밤과 낮을 번갈아 진행한다. 생존자가 짝수 명이면 밤이고, 홀수 명이면 낮이다. 마피아가 사라지면 시민이 이기고, 시민이 모두 사라지면 마피아가 이긴다. 이 조건이 만족되는 즉시 게임은 끝난다.

각 참가자에게는 유죄 지수가 있다. 낮에는 생존자 중 유죄 지수가 가장 높은 참가자가 죽는다. 그런 참가자가 여러 명이면 번호가 가장 작은 참가자가 죽는다. 낮에는 유죄 지수가 변하지 않는다.

밤에는 은진이가 죽일 참가자 한 명을 고른다. 참가자 i가 밤에 죽으면, 다른 참가자 j의 유죄 지수는 R[i][j]만큼 변한다.

은진이가 매번 최적으로 선택하여 게임을 최대한 오래 끌 때, 지나갈 수 있는 밤의 최대 횟수를 구하라.

첫째 줄에 참가자 수 N이 주어진다.

둘째 줄에 각 참가자의 유죄 지수 N개가 주어진다.

다음 N개 줄에는 반응 배열 R이 주어진다. 각 줄에는 정수 N개가 있으며, i번째 줄의 j번째 수가 R[i][j]이다.

마지막 줄에 은진이의 참가자 번호가 주어진다.

N은 16 이하의 자연수이다. 유죄 지수는 300 이상 800 이하의 자연수이다. R에 있는 모든 수는 절댓값이 1 이상 26 이하인 정수이다.

은진이가 최적으로 플레이할 때 지나갈 수 있는 밤의 최대 횟수를 출력한다.