Bond P60515

Todo el mundo conoce al agente secreto 007, el famoso Bond, James Bond. Mucho menos conocido es el hecho que no completó él mimso muchas de sus misiones, sinó que fueron varios de sus primos Jimmy Bonds (sí, todos ellos se llaman Jimmy, como su abuelo). Bond (James Bond) tiene mucho trabajo distribuyendo misiones a los Jimmy Bonds cada vez que le asignan una nueva, por lo que te solicita tu ayuda.

Cada mes Bond (James Bond) recibe una lista de misiones. Para cada misión y para cada uno de sus primos Jimmy, Bond (James Bond) conoce la probabilidad que dicho primo la resuelva. Tu programa debe obtener la asignación de misiones a Jimmy Bonds que resulte en la máxima probabilidad que todas las misiones se completen con éxito. Hay el mismo número de Jimmy Bonds que de misiones, y cada Jimmy puede ser asignado a una única misión.

Recuerda que la probabilidad que todas las misiones tengan éxito es igual al producto de las probabilidades de tener éxito en cada una de las misiones individualmente.

Entrada

La primera línea contiene un número 1≤ N ≤ 20, el número de Jimmy Bonds y de misiones. Las siguientes N líneas contienen N enteros entre 0 y 100, inclusive. El j-ésimo entero en la línea i-ésima contiene la probabilidad (en porcentaje) de que el Jimmy Bond número i complete con éxito la misión j.

Salida

Escribe una línea con la máxima probabilidad (en porcentaje, y con exactamente dos decimales) de que todos los Jimmy Bonds completenen todas las misiones.

Observación

Para escribir doubles con 2 dígitos de precisión, usa cout.setf(ios::fixed); cout.precision(2); en C++, o printf("%.2f", ...); en C.