제퍼디

시간 제한2초메모리 제한512 MB

요약

n x n 격자에서 두 사람이 번갈아 행 하나와 열 하나를 지워 마지막 한 칸이 남을 때까지 진행하며, 선수는 그 칸의 값을 최대화하고 상대는 최소화한다.

난이도: 보통10점 중 7점
유형: 게임 이론, 그리디, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

당신은 지적 게임의 결승전을 치르고 있다. 총 $n$ 개의 주제가 선정되었고, $n$ 명의 출제자 각각이 모든 주제에 대해 문제를 하나씩 준비했다. 각 주제 $i$ 와 각 출제자 $j$ 에 대해, 주제 $i$ 에서 출제자 $j$ 의 문제를 맞힐 확률을 알고 있다.

실제로 문제를 받기 전까지 $n - 1$ 번의 턴이 진행된다. 각 턴에서는 두 가지 행동이 일어난다. 먼저 당신이 어떤 주제 하나의 문제를 모두 버린다. 그다음 진행자가 어떤 출제자 한 명의 문제를 모두 버린다. 결국 문제 하나만 남는다. 그것을 맞히면 라운드에서 승리한다.

물론 당신은 승리 확률을 최대화하려고 열을 버린다. 반대로 진행자는 그 확률을 최소화하려고 한다.

둘 다 최적으로 플레이할 때, 남은 문제를 맞힐 확률은 얼마인가?

입력

첫째 줄에 정수 $n$ ( $1 \le n \le 500$ )이 주어진다. 이는 주제의 수이자 출제자의 수이다. 이어서 $n$ 개의 줄이 주어지고, 각 줄에는 $n$ 개의 정수가 있다. $i$ 번째 줄은 $i$ 번째 주제에 대응하며, 그 줄의 $j$ 번째 수는 출제자 $j$ 의 문제를 맞힐 확률이다.

확률은 백분율로 주어진다. 주제 설명에 나오는 모든 정수는 0과 100 사이이다.

출력

원하는 확률을 백분율로 나타낸 수 하나를 출력한다.

예제2

예제 1
입력
```
2
1 100
99 0
```
예상 출력
```
1
```
예제 2
입력
```
3
0 50 100
100 0 50
50 100 0
```
예상 출력
```
0
```