시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 370 66 34 13.821%

문제

은진이는 요즘 마피아라는 게임에 빠져있다. 이 게임의 규칙은 다음과 같다.

1. 플레이어는 두 그룹으로 나누어진다. 한 그룹은 마피아이고, 또다른 그룹은 선량한 시민이다. 마피아의 정체는 시민에게 알려져 있지 않다.

2. 플레이어가 짝수명 남았을 때는 밤이다. 밤에는 마피아가 죽일 사람 한 명을 고른다. 죽은 사람은 게임에 더이상 참여할 수 없다.

3. 플레이어가 홀수명 남았을 때는 낮이다. 낮에는 플레이어가 가장 죄가 있을거 같은 사람 한 사람을 죽인다.

4. 만약 게임에 마피아가 한 명도 안 남았다면, 그 게임은 시민팀이 이긴 것이고, 시민이 한 명도 안남았다면, 그 게임은 마피아팀이 이긴 것이다. 게임은 즉시 종료된다.

게임을 잠시동안 한 후에 은진이는 지금 현재 이 게임에서 자기가 마지막으로 남은 마피아라는 것을 알았다. 따라서 은진이는 이 게임을 이기기위해 방법을 생각하기 시작했다.

일단 은진이에게는 각 사람의 유죄 점수가 주어진다. 이 유죄 점수는 낮에 시민들이 어떤 플레이어를 죽일건지 고를 때 쓰인다. 그리고 대답이 주어진다. 대답(R)은 2차원 배열이다.

게임은 다음과 같이 진행된다.

1. 밤에는 마피아가 죽일 사람을 한 사람 고른다. 이것으로 인해 각 사람의 유죄 점수가 바뀐다. 만약 플레이어 i가 죽었다면, 다른 플레이어 j의 유죄 점수는 R[i][j]만큼 변한다.

2. 낮에는 현재 게임에 남아있는 사람 중에 유죄 점수가 가장 높은 사람을 죽인다. 만약 같을 경우에는 플레이어의 번호가 낮은 사람이 죽는다.

은진이의 플레이어 번호가 주어졌을 때, 은진이는 되도록이면 이 게임을 오래하고 싶다. 은진이가 이 게임을 정말 천재적으로 매번 가장 최적의 선택을 할 때, 몇 번의 밤이 지나는지 출력하는 프로그램을 작성하시오. 플레이어의 번호는 0번부터 시작한다.
 

입력

첫째 줄에 플레이어의 수 N이 주어진다. N은 둘째 줄에는 현재 각 플레이어의 유죄 점수가 주어진다. 셋째 줄부터 N개의 줄에는 배열 R이 주어진다. 마지막 줄에는 은진이의 플레이어 번호가 주어진다. N은 16보다 작거나 같은 자연수이고, 유죄 점수는 300보다 크거나 같고, 800보다 작거나 같은 자연수이다. R배열에 있는 숫자는 모두 절댓값이 1보다 크거나 같고 26보다 작거나 같은 0이 아닌 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력

4
500 500 500 500
1 4 3 -2
-2 1 4 3
3 -2 1 4
4 3 -2 1
1

예제 출력

2

힌트

출처