Đề bài

Wreauter đang tham gia chương trình huấn luyện SWAT tại hành tinh Emearmy, nơi cậu đóng vai trò đội trưởng của một đội gồm \(N\) thành viên (đánh số từ \(1\) đến \(N\)). Mỗi thành viên sẽ được giao đúng một nhiệm vụ từ danh sách \(N\) nhiệm vụ, sao cho mỗi nhiệm vụ cũng chỉ được giao cho một người.

Cậu có bảng \(P\) gồm \(N \times N\), trong đó \(P_{i,j}\) là xác suất thành công (theo %) khi giao nhiệm vụ \(j\) cho thành viên \(i\).

Xác suất thành công của toàn bộ kế hoạch là tích các xác suất thành công của từng cặp thành viên - nhiệm vụ.

Hãy giúp Wreauter tìm cách phân công nhiệm vụ sao cho xác suất thành công của toàn đội là lớn nhất.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(N \leq 20\))
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên \(P_{i,j}\) (\(0 \leq P_{i,j} \leq 100\))

Dữ liệu ra

• In ra xác suất thành công lớn nhất của toàn đội (theo %) với sai số tối đa \(10^{-6}\).

Giới hạn

• Subtask 1: (50%) \(N \leq 10\)
• Subtask 2: (50%) Không có giới hạn thêm

Sample Input 1

2
100 100
50 50

Sample Output 1

50

Sample Input 2

3
25 60 100
13 0 50
12 70 90

Sample Output 2

9.1

Giải thích

• Input 1: Giao nhiệm vụ đầu tiên cho thành viên 1, nhiệm vụ 2 cho thành viên 2. Xác suất thành công là \(100\% \times 50\% = 50\%\).
• Input 2: Cách tối ưu là:
  • Thành viên 1 làm nhiệm vụ 3 (\(100\%\))
  • Thành viên 2 làm nhiệm vụ 1 (\(13\%\))
  • Thành viên 3 làm nhiệm vụ 2 (\(70\%\)) → Xác suất thành công: \(100 \times 13 \times 70 / (100^2) = 9.1\%\)