Adventures#231
Everyone knows about Indiana Jones's legendary adventures. As usual, in search of adventure, Jones gets into a difficult situation. Now he is in an ancient Indian temple. There is a map of the temple depicted on the wall of the temple hall. The temple consists of many rooms connected by one-way passageways (corridors).
According to ancient chronicles, if someone either passes through all the rooms or finds the treasure, the temple is destroyed and an escape to freedom is possible. It is also known that if you enter or exit any room, the ceiling in that room collapses, and it is impossible to pass through that room in the future. The map shows all the rooms of the temple, the tunnels between them, and the probability that there is a treasure in each room.
Indiana, like everyone, is lazy and asks you to solve this task. It is necessary to minimize the expected average path length traversed through tunnels. He also reports that he can teleport to any room.
You need to find the way that achieves the minimum expected distance across all rooms. If there is no way of covering all rooms, you must inform Jones, as in this case, he may never be able to return from the temple.
The input file contains several tests. Each test is a map of the temple. The first line of each test contains the number 1 \leq N \leq 100 — the number of rooms. Then follow lines, each containing integers a_{ij} (|a_{ij}| < 1000). If the number a_{ij} is written in the -th row and -th position, this means there is a tunnel of length a_{ij} from room to room . If a_{ij} is less than zero, this means the tunnel is blocked and cannot be used. The next line contains numbers p_i. The number p_i is the probability that room contains the treasure.
The last test has N = 0 and should not be processed.
For each test, output the expected distance with three digits after the decimal point. If there is no way of covering all rooms, print -1.
Example 1