В новый офис привезли N компьютеров. Расположенный рядом радиотелескоп не позволяет использовать Wi-Fi для связи, и хелпдеску придётся организовывать сеть с помощью LAN-кабелей. Собрав все завалявшиеся по углам кабели, админы сумели соединить K пар компьютеров. Утомившись после длинного рабочего дня, сотрудники хелпдеска обратились к вам за помощью — рассчитать бюджет, необходимый для завершения задачи. Так у вас появился список из M пар компьютеров, которые могут соединить админы, и стоимость каждого кабеля. Начав работу, вы обнаружили баг в системе расчёта стоимости — вместо сложения стоимостей, они умножаются — так кабель стоимостью 4 и кабель стоимостью 3 вместе стоят не 7, как подсказывает логика, а 12. Для выполнения задачи вам необходимо рассчитать стоимость кабелей, достаточных для организации связной сети — такой, что каждый компьютер соединён с каждым прямо или опосредованно.

Формат ввода
Первая строка содержит числа 0 < N < 106, 0 ≤ K < 106, 0 ≤ M < 106.
Следующие N строк содержат описание уже соединенных компьютеров. Каждая строка содержит чиcло Au - количество компьютеров, соединенных с компьютером u. Следующие Au чисел в этой строке 1 ≤ v ≤ N описывают номера компьютеров, уже соединенных с компьютером v. Сумма Au равна K.
Следующие N строк содержат описание компьютеров, которые можно соединить. Каждая строка содержит чиcло Bu - количество компьютеров, которые можно соединить с компьютером u. Следующие Bu пар чисел в этой строке 1 ≤ v ≤ N, 1 ≤ p ≤ 109 описывают номера компьютеров, которые можно соединить кабелем стоимостью p. Сумма Bu равна M.

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

Пример 1
Ввод	Вывод
2 0 1
0
0
1 2 9
0
9