Гости с Тау Кита
Организаторы Кубка Векуа были изрядно удивлены, когда среди заявок на участие в соревнованиях оказалась заявка команды с Тау Кита. Однако заявка была оформлена по всем правилам, и таукитяне были включены в списки. В Батуми они собирались прибыть на своём космическом корабле. Для коммуникации с приближающимся кораблём таукитяне предложили установить стационарный лазер и использовать некий аналог азбуки Морзе.
Однако в день прибытия возникла неожиданная сложность: на небе появились плотные облака, которые, проходя над установкой, закрывали луч лазера. Для того, чтобы сделать поправку на вызванные облаками ошибки, гости подали срочный запрос в жюри соревнований: какое наибольшее число раз луч лазера будет закрыт? К сожалению, жюри не знает место установки лазера - это дело оргкомитета, да и из прогноза погоды известно только, что ветер будет дуть с постоянной скоростью. Но положение облаков на небе жюри определить может. Поэтому было принято решение сообщить наибольшее для всех возможных расположений лазера и направлений ветра количество закрытий луча. Вам поручено написать программу, вычисляющую это количество.
Для упрощения задачи поверхность земли считается плоской, проекция каждого облака на землю представляется в виде многоугольника с целыми вершинами, все проекции считаются попарно непересекающимися, а ветер с постоянной скоростью смещает все имеющиеся облака вдоль некоторого вектора параллельно поверхности земли. Лазер представляется точкой на плоскости. Считается, что облако закрывает лазер, если точка, его представляющая, лежит на границе или внутри проекции облака.
Входные данные
В первой строке входного файла записано число n - количество облаков на небе. Далее идёт n строк, описывающих проекции отдельных облаков: в i-й строке сначала идёт количество n_i > 3 вершин в многоугольнике, представляющем i-е облако, затем 2n_i координат этих вершин -10^9 ≤ x_i, y_i ≤ 10^9. При этом суммарное количество вершин многоугольников для всех облаков, заданных во входном файле, не превышает 2000.
Выходные данные
Одно число k - максимальное количество перебоев в видимости лазера, вызванных облаками.
В случае, показанном в примере, максимальный ответ 3 достигается, например, при размещении лазера в точке (0, 4) и ветре, направленном вдоль вектора [-1, 0].