Problems
Карточный поединок Junior
Карточный поединок Junior
Двое игроков играют в игру. Каждый из игроков изначально получает некоторое количество карт (пусть будет \textbf{n_1} и \textbf{n_2} соответственно). Каждый ход игроки выбирают по одной из имеющихся у них на руках карт, и затем открывают их. Более слабая карта сбрасывается в отбой, а более сильную игрок, показавший ее, забирает обратно. В случае, если игроки показали одинаковые карты, они обе сбрасываются в отбой. Игра продолжается до тех пор, пока хотя бы у одного из игроков не закончатся карты. Если при этом у одного из игроков осталась еще хотя бы одна карта, он получает \textbf{1} очко, а соперник -- \textbf{0}. Если же у обоих игроков закончились карты, каждый получает по \textbf{0.5} очков. Всего есть \textbf{N} типов карт. Отношение силы карт может быть не транзитивным и задается матрицей \textbf{A}. \textbf{A_\{ij \}}равно \textbf{1}, если карта \textbf{i} бьет карту \textbf{j}, и \textbf{0} в противном случае. Требуется определить максимальный средний выигрыш игрока в предположении, что второй игрок использует равномерную стратегию (то есть каждый ход выбирает одну из своих карт случайно с равной вероятностью).
\textbf{Ограничения}
\textbf{1} ≤ \textbf{n_1}, \textbf{n_2}, \textbf{N} ≤ \textbf{8}. \textbf{A_ij + A_ji =1} при \textbf{i} ≠ \textbf{j}, \textbf{A_ii =0}.
\InputFile
В первой строке задается число \textbf{N}. Последующие \textbf{N} строк содержат по \textbf{N} чисел, определяющих матрицу \textbf{A}. Следующая строка содержит число \textbf{n_1} и еще \textbf{n_1} чисел, каждое из которых определяет тип соответствующей карты первого игрока. В последней строке в аналогичном формате задаются карты второго игрока.
\OutputFile
Выведите цену игры для первого игрока с точностью не менее \textbf{10^\{-8\}}.
Input example #1
3 0 1 1 0 0 1 0 0 0 2 3 2 1 1
Output example #1
0.00000000