NBA One-on-One Challenge

NBA legends face off in a series of one-on-one matches. There are m opponents plus Kobe. Before the games, each opponent is assigned an ability value. The competition is played over m rounds. In the i-th round, Kobe faces one opponent (each opponent can be faced only once) and his probability of winning against opponent j in round i is given by p_i,j.

The overall probability that Kobe wins all matches is given by \[ P = \prod_{i=1}^{m} p_{i,\pi(i)}, \] where \(\pi\) is the permutation (ordering) of opponents.

Kobe wants to choose an order of opponents that maximizes his overall win probability. Among all orders that achieve the maximum overall win probability (with an absolute error tolerance of \(10^{-10}\)), determine the maximum possible sum of the ability values of the opponents he beats. (Note that once an opponent is defeated, he does not participate in further rounds.)

Input and Output Format:

The input starts with an integer m. The next line contains m integers representing the ability values of the opponents. This is followed by m lines, each containing m real numbers. The j-th number in the i-th line represents the probability p_i,j that Kobe wins against opponent j in round i.

The output is a single number – the maximum total ability value of the opponents defeated under the condition that the overall win probability is maximized.

inputFormat

The first line contains an integer m (the number of opponents).

The second line contains m space-separated integers, where the j-th integer is the ability value of opponent j.

The next m lines each contain m space-separated real numbers. The j-th number in the i-th line represents p_i,j, the probability that Kobe wins against opponent j in round i.

outputFormat

Output a single number — the maximum total ability value of the opponents Kobe can defeat, given that his overall win probability is maximized (with tolerance \(10^{-10}\)).

sample

3
10 20 30
0.9 0.8 0.7
0.6 0.95 0.8
0.5 0.6 0.99

60