Все знают о приключенческих историях Индианы Джонса.
Как обычно, в поисках приключений, Джонс попадает в сложные ситуации. Теперь он в древнем индейском храме. В зале храма на стене изображена карта храма. Храм – это множество комнат, соединенных коридорами, сделанными так, что по ним можно ходить только в одном направлении. Согласно летописям, если кто-либо пройдет по всем комнатам или найдет сокровище, храм разрушится и можно будет выйти на свободу. Так же известно, что если вы войдете или выйдете из любой комнаты, потолок в этой комнате обрушится, и пройти через эту комнату в будущем будет невозможно. Карта определяет все комнаты храма и туннели между ними, а также вероятность, что в некоторой комнате будет находиться сокровище.
Индиана – ленив как все люди, и просит решить задачу. Необходимо минимизировать средний ожидаемый путь, проходимый по туннелям.
Он также сообщил, что может телепортироваться в любую комнату.
Вам необходимо найти путь, в котором мы получим минимальное ожидаемое расстояние по всем комнатам.
Если нет пути, содержащего все комнаты, нужно проинформировать Джонса, поскольку в этом случае возможно, что Джонс никогда не вернется из храма.

Входной файл содержит несколько тестов. Каждый тест – это карта храма. В первой строке каждого теста записано число 1  N  100 – количество комнат в храме. После этого идут N строк по N чисел aij в каждом (|aij| < 1000). Если в строке i в позиции j записано число aij, это означает, что из комната i в комнату j есть туннель длины aij. Если число aij меньше нуля, это означает, что туннель завален и по нему нельзя пройти.
Затем следует строка, содержащая N чисел pi. Число pi – это вероятность, что в комнате с номером i будет сокровище.
Последний тест имеет N = 0 и не должен обрабатываться

Для каждого теста выведите среднее расстояние с тремя знаками после точки.
Если не существует пути, содержащего все комнаты, выведите -1.

4
1 1 -1 -1
-1 1 2 -1
-1 -1 1 3
-1 -1 -1 1
0.1 0.7 0.3 0.4
3
1 1 -1
-1 1 -1
-1 1 1
0.1 0.2 0.3
0

2.947
-1