Задача номер 9. Возведение Старгородского трамвая

9. Возведение Старгородского трамвая

Виктору Михайловичу Полесову после закупки партии плашек в три восьмых дюйма пришла следующая партия — в две седьмых дюйма. Он и призадумался — три восьмых да две седьмых это же будет тридцать семь пятьдесят шестых... А если следом придут плашки со знаменателем дроби девять, то оперировать уже придется с кучей дробей с единым знаменателем пятьсот четыре и так далее. Тут-то перед ним и стала во всём своем ужасе картина его грядущей деятельности по возведению Старгородского трамвая. А именно: каждую неделю ему придется решать задачу — какой комплект плашек (с каким знаменателем) из предложенных закупить для продолжения строительства.

Цель же гусара-одиночки с мотором — получить в итоге своей деятельности как можно больший наименьший общий знаменатель для всех партий плашек.

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

В первой строке входного файла записано целое число N — количество недель, на протяжении которых Виктор Михайлович выбирает знаменатели в партиях плашек (1 <= N <= 20).

В следующих N строках дано описание каждой из N недель поставок плашек.

Первым в каждой строке записано целое число ki, задающее количество комплектов, предложенных на i-ой неделе (1<= ki <= 20), после него через пробел задаются ki целых чисел aij — соответственно знаменатели в j-ой партии на i-ой неделе (1 <= aij <= 42).

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

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

Пример

input.txt
3
2 4 6
3 1 5 8
2 7 10

output.txt
210

Соревнование: XI Открытая Всесибирская олимпиада по программированию имени И.В. Поттосина 2010
Источник: http://olimpic.nsu.ru