Пригоди
Усі знають про пригоди Індіани Джонса. Як завжди, у пошуках нових викликів Джонс опиняється в складних ситуаціях. Цього разу він у стародавньому індіанському храмі. На стіні в залі храму зображена карта. Храм складається з багатьох кімнат, з'єднаних коридорами, якими можна рухатися лише в одному напрямку. Згідно з літописами, якщо хтось пройде через усі кімнати або знайде скарб, храм зруйнується, і можна буде вийти на свободу. Також відомо, що якщо ви увійдете або вийдете з будь-якої кімнати, стеля в цій кімнаті обвалиться, і пройти через неї знову буде неможливо. Карта показує всі кімнати храму і тунелі між ними, а також ймовірність того, що в деякій кімнаті знаходиться скарб. Індіана, як і всі люди, не любить зайвих зусиль, тому просить вас вирішити цю задачу. Потрібно мінімізувати середню очікувану довжину шляху, яким він пройде через тунелі. Він також повідомив, що може телепортуватися в будь-яку кімнату. Вам потрібно знайти шлях, який забезпечить мінімальну очікувану відстань по всіх кімнатах. Якщо немає шляху, що охоплює всі кімнати, потрібно повідомити Джонса, оскільки в такому випадку він може ніколи не повернутися з храму.
Вхідний файл містить кілька тестів. Кожен тест — це карта храму. У першому рядку кожного тесту записано число 1 ≤ N ≤ 100 — кількість кімнат у храмі. Далі йдуть N рядків по N чисел aij у кожному (|aij| < 1000). Якщо в рядку i на позиції j записано число aij, це означає, що з кімнати i в кімнату j є тунель довжини aij. Якщо число aij менше нуля, це означає, що тунель завалений і пройти по ньому неможливо. Потім слідує рядок, що містить N чисел pi. Число pi — це ймовірність, що в кімнаті з номером i буде скарб. Останній тест має N = 0 і не повинен оброблятися.
Для кожного тесту виведіть середню відстань з трьома знаками після коми. Якщо не існує шляху, що охоплює всі кімнати, виведіть -1.