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

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

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