Японский стиль паб

Вы только что вошли в японский паб, или изакаю, чтобы провести вечер в компании друзей на традиционной вечеринке с выпивкой, называемой номи-кай.

Вам предстоит сделать заказы на алкогольные и безалкогольные напитки по просьбе участников. Однако, к сожалению, большинство сотрудников в типичных изакаях работают неполный рабочий день и не всегда хорошо справляются со своей работой, поэтому вероятность ошибки в каждом заказе существует.

Вы обеспокоены возможными ошибками. Сегодня важный день для участников, ваших дорогих друзей.

Ваша задача — написать программу, которая вычислит вероятность того, что персонал изакаи принесет правильные напитки для всех заказов. Случаи, когда ошибки персонала приводят к правильной доставке, также должны учитываться в вероятности, так как они для вас приемлемы.

Входные данные

Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай начинается с строки, содержащей целое число N (1 ≤ N ≤ 8).

Целое число N указывает количество видов напитков, доступных в изакае.

Следующие N строк содержат вероятности для напитков в формате, показанном ниже.

p_11 p_12 ··· p_1N p_21 p_22 ··· p_2N ··· p_N1 p_N2 ··· p_NN

Каждое действительное число p_ij указывает вероятность того, что персонал доставит стакан напитка j для заказа напитка i. Выполняется условие p_ij ≥ 0 и p_i1 + p_i2 + ··· + p_iN = 1 для 1 ≤ i, j ≤ N. В конце каждого тестового случая идет строка, содержащая N. i-е целое число n_i представляет количество заказов на напиток i от участников (0 ≤ n_i ≤ 4).

Последний тестовый случай завершается строкой, содержащей ноль.

Выходные данные

Для каждого тестового случая напечатайте строку, содержащую номер тестового случая (начиная с 1), за которым следует натуральный логарифм вероятности того, что персонал принесет правильные напитки для всех заказов. Выведите результаты с восемью знаками после запятой. Если персонал не может принести правильные напитки ни в одном случае, выведите "-INFINITY". Используйте формат из примера вывода.