Agent Mission Assignment

Time limit1sMemory limit128 MB

Summary

Given an N x N matrix of success percentages, assign one mission per agent to maximize the product of chosen probabilities, essentially an assignment problem with a product (log-sum) objective.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Combinatorics
Solved: No attempts yet

Problem

Secret agent 007 receives several missions every month and assigns them one by one to cousin agents who look like him. The number of agents and the number of missions are both N.

For each agent i and mission j, the probability that agent i successfully completes mission j is given as a percentage. Each agent must be assigned exactly one mission, and each mission must be assigned to exactly one agent.

The probability that all missions succeed is the product of the success probabilities of the assigned missions. Find the maximum possible probability that all missions succeed.

Input

The first line contains N, the number of missions and agents. (1 <= N <= 20)

Each of the next N lines contains N integers between 0 and 100, inclusive. The jth integer on the ith line is the probability, in percent, that agent i successfully completes mission j.

Output

Print the maximum probability, as a percentage, that all missions can be completed successfully. An absolute or relative error up to 0.000001 is allowed.

Examples3

Example 1
Input
```
2
100 100
50 50
```
Expected output
```
50.000000
```
Example 2
Input
```
2
0 50
50 0
```
Expected output
```
25.00000
```
Example 3
Input
```
3
25 60 100
13 0 50
12 70 90
```
Expected output
```
9.10000
```