Пригоди#231
Усі знають про легендарні пригоди Індіани Джонса. Як завжди, у пошуках пригод Джонс опиняється в складній ситуації. Тепер він у стародавньому індіанському храмі. На стіні залу храму зображена карта храму. Храм складається з багатьох кімнат, з'єднаних односторонніми проходами (коридорами).
Згідно з давніми хроніками, якщо хтось або пройде через усі кімнати, або знайде скарб, храм зруйнується, і можна буде вибратися на свободу. Також відомо: якщо ви входите або виходите з будь-якої кімнати, стеля в цій кімнаті обвалюється, і пройти через неї надалі буде неможливо. Карта показує всі кімнати храму, тунелі між ними та ймовірність того, що в кожній кімнаті є скарб.
Індіана, як і всі, лінивий і просить вас розв'язати цю задачу. Необхідно мінімізувати очікувану середню довжину шляху, пройденого тунелями. Також йому відомо, що він може телепортуватись в будь-яку кімнату.
Вам потрібно знайти шлях, який дозволить отримати мінімальну очікувану відстань по всіх кімнатах. Якщо немає шляху, що охоплює всі кімнати, слід проінформувати Джонса, адже в такому разі він може ніколи не повернутись із храму.
Вхідний файл містить кілька тестів. Кожен тест — це карта храму. У першому рядку кожного тесту записано число 1 \leq N \leq 100 — кількість кімнат у храмі. Далі йдуть рядків по чисел a_{ij} (|a_{ij}| < 1000). Якщо у -му рядку на -ій позиції записано число a_{ij}, це означає, що є тунель довжини a_{ij} з кімнати в кімнату . Якщо a_{ij} менше нуля, тунель завалений і ним скористатись неможливо. Наступний рядок містить чисел p_i. Число p_i — ймовірність, що у -й кімнаті міститься скарб.
Останній тест має N = 0 і не повинен оброблятись.
Для кожного тесту виведіть очікувану відстань з трьома знаками після десяткової крапки. Якщо не існує шляху, що охоплює всі кімнати, виведіть -1.
Приклад 1