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