Охотник Боб часто гуляет со своей собакой Ральфом. Боб гуляет с постоянной скоростью и его путь – ломаная (возможно, самопересекающаяся), каждая вершина которой задается двумя целыми числами ( X _i , Y _i ) – декартовыми координатами.

Ральф бегает сам по себе, но обязательно должен встречаться с хозяином в указанных N точках. Собака начинает свой путь одновременно с хозяином в точке ( X ₁ , Y ₁ ) и завешает его вместе с хозяином в точке ( X _N , Y _N ) .

Ральф может бегать с любой скоростью, не превышающей в два раза скорость Боба. Пока Боб идет по прямой из точки в точку, собака ищет деревья, кусты, холмики и прочие интересные места, которые заданы парами целых чисел ( X ^' _j , Y ^' _j ) . Всего таких мест M. Тем не менее, покидая своего хозяина в точке ( X _i , Y _i ) (где 1 ≤ i ≤ N ), Ральф посещает не более одного интересного места перед тем, как опять встретить хозяина в точке ( X _{i + 1} , Y _{i + 1} ) .

Ваша задача – найти маршрут, удовлетворяющий указанным выше условиям, с максимальным количеством посещаемых интересных мест. Он представляется ломаной, по которой бегает Ральф. Ее вершинами должны быть все точки ( X _i , Y _i ) и посещенные интересные места ( X ^' _j , Y ^' _j ) . Последние должны быть посещены (то есть встречаться в описании пути) не более одного раза.

Пример пути Боба (сплошная линия), набора интересных мест (точки) и одного из лучших путей Ральфа представлены на рисунке:

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

В один солнечный день главный камень одной из площадок обратил внимание, что вокруг стало очень тесно. Но камни не могут катиться вверх, а на нижние площадки они катиться не хотят из-за плохого рейтинга. Поэтому главный камень пошел на хитрость. Он выбрал M камней и сказал каждому из них, что где-то внизу появилась замечательная площадка с самым высоким рейтингом на горе. Для полной правдоподобности он составил карту площадок, на которые можно скатиться с его площадки. Всего (включая переполненную площадку) оказалось N площадок. Поскольку главный камень ленивый, он не стал рисовать все пути между площадками, а просто нарисовал минимальное количество проходов между площадками, чтобы из его площадки можно было добраться в любую, находящуюся ниже. Он показал каждому из M камней эту карту и объяснил, где находится замечательная площадка (чтобы камень запомнил путь). Причем, чтобы главные камни нижних площадок не имели к нему претензий из-за такого нашествия, некоторым камням он показал на другие площадки, чем остальным. Чтобы не создать лавину, он сказал камням катиться с небольшим интервалом между собой. Немного подумав, он решил, что можно пускать камни парами, чтобы пространство быстрее освободилось. Камни ему поверили и стали собираться в дорогу.

Камни не любят скучать, поэтому каждая пара решила посчитать, сколько времени они будут катиться вместе, и, может быть, перестроить пары, чтобы увеличить это время. На то, чтобы скатиться по проходу с одной площадки в следующую, не заходя по пути на другие площадки, камень тратит одну минуту. Но складывать числа камни не умеют, в этом им требуется ваша помощь.

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

В один солнечный день главный камень одной из площадок обратил внимание, что вокруг стало очень тесно. Но камни не могут катиться вверх, а на нижние площадки они катиться не хотят из-за плохого рейтинга. Поэтому главный камень пошел на хитрость. Он выбрал M камней и сказал каждому из них, что где-то внизу появилась замечательная площадка с самым высоким рейтингом на горе. Для полной правдоподобности он составил карту площадок, на которые можно скатиться с его площадки. Всего (включая переполненную площадку) оказалось N площадок. Поскольку главный камень ленивый, он не стал рисовать все пути между площадками, а просто нарисовал минимальное количество проходов между площадками, чтобы из его площадки можно было добраться в любую, находящуюся ниже. Он показал каждому из M камней эту карту и объяснил, где находится замечательная площадка (чтобы камень запомнил путь). Причем, чтобы главные камни нижних площадок не имели к нему претензий из-за такого нашествия, некоторым камням он показал на другие площадки, чем остальным. Чтобы не создать лавину, он сказал камням катиться с небольшим интервалом между собой. Немного подумав, он решил, что можно пускать камни парами, чтобы пространство быстрее освободилось. Камни ему поверили и стали собираться в дорогу.

Камни не любят скучать, поэтому каждая пара решила посчитать, сколько времени они будут катиться вместе, и, может быть, перестроить пары, чтобы увеличить это время. На то, чтобы скатиться по проходу с одной площадки в следующую, не заходя по пути на другие площадки, камень тратит одну минуту. Но складывать числа камни не умеют, в этом им требуется ваша помощь.

В маленьком городке М начала действовать служба контроля за незаконными полетами НЛО. Первая задача службы — выяснить, сколько НЛО действует в окрестности города. Агенты службы опросили множество свидетелей и составили список случаев встречи с НЛО, произошедших за одни сутки, с указанием места и времени наблюдения. Теперь аналитики хотят понять, сколько же на самом деле было НЛО. Из данных разведки известна максимальная скорость, с которой может лететь НЛО. Аналитики просят вас узнать, какое минимальное количество НЛО могли наблюдать свидетели.

На одной из планет, под названием TheBestWorld, живут много умных людей. Эта планета также известна своими двумя конкурирующими школами супергероев. Каждый малыш, живущий на этой планете, мечтает стать супергероем, но не у всех это получается.

Ученики разных школ всегда недолюбливали друг друга. И иногда дело даже доходило до того, как супергерои начали применять свои геройские силы для выяснения отношений.

В этом мире случилось несчастье. На TheBestWorld нападают темные силы. У генерала главнокомандующего армией супергероев есть в распоряжении n + m супергероев, из них n — выпускники первой школы, m — второй. Главнокомандующий подсчитал количество супергероев k , которые смогут спасти лучшее, что у них есть, — планету.

На первый взгляд кажется, что главнокомандующему не понадобится помощь в выборе супергероев, но он вспомнил, что супергерои из разных школ раздражают друг друга. Но это происходит только тогда, когда два супергероя из разных школ находятся на расстоянии меньше d . Если такую пару героев позвать спасать мир, они не смогут продуктивно делать свою работу.

Проблема в том, что генерал забыл искомое d . Вам известны координаты каждого из супергероев. Генерал просит вас вычислить максимальное d , при котором он все еще может спасти мир. И выдать список супергероев, которые спасут мир при данном d .