кратчайшие пути

В реальных компьютерных сетях также используется понятие максимальной единицы передачи (MTU, maximum transmission unit) - размер блока данных, который может быть передан на отрезке сети между двумя устройствами. Этот размер зависит от ограничений используемой технологии
передачи данных на нижнем уровне.
В данной задаче требуется составить оптимальный план передачи пакетов с учётом MTU между разными маршрутизаторами и вычислить минимальное время передачи на его основе.
Нужно иметь в виду, что окно передачи работает по "скользящему" принципу, то есть после получения подтверждения доставки первых байтов окна оно сдвигается вправо на размер доставленной информации.

Входные данные
В первой строке записано натуральное число N, не превышающее 100 - количество маршрутизаторов. Далее записано N таблиц маршрутизации в следующем формате: в первой строке число N1 - количество маршрутов в таблице, далее N1 строк, где через пробел указаны адрес сети, маска (целое число от 1 до 32), номер маршрутизатора, куда будет отправлен пакет (номера считаются с 1 по порядку описания), время передачи до следующего маршрутизатора в миллисекундах и MTU в байтах.
После описания таблиц маршрутизации в следующей строке записаны через пробел адрес узла-отправителя, номер маршрутизатора, к которому он подключён, адрес узла-получателя, номер маршрутизатора, к которому подключён получатель, и объём данных (в байтах), который требуется передать.

Выходные данные
Минимальное время передачи в миллисекундах.
Примечание: считать, что между получением каждого пакета и отправкой подтверждения с конечного устройства всегда проходит 1 мс.
Примечание 2: считать, если объём данных, который требуется отправить с одного маршрутизатора на другой, превышает MTU, то данные делятся на пакеты, равные максимальной единице передачи или меньше, и отправляются с задержкой в 1 мс.
В рамках данной задачи считать, что потери отсутствуют и все отправленные пакеты достигают получателя, а также что размер окна фиксированный и составляет 10240 байт. Также следует пренебречь временем передачи данных между конечными узлами и ближайшими
маршрутизаторами и размером пакета ACK (считать, что он меньше любого MTU).

Примеры

№	Входные данные	Выходные данные
1	5 3 10.0.0.0 8 2 10 100 20.0.0.0 8 3 10 100 10.0.0.0 8 5 10 10240 1 10.0.0.0 8 4 10 100 1 30.0.0.0 8 4 10 100 1 40.0.0.0 8 1 10 100 1 10.0.0.0 8 4 20 10240 40.1.1.1 1 10.1.1.1 4 102400	410

Примечание
Если отправлять пакеты с 1-го маршрутизатора на 5-й, то время передачи каждых 10240 байт с учётом подтверждения займёт 41 мс. Если же отправлять с 1-го через 2-й, то 10240 байт окна передачи будут делиться на 103 блока и суммарное время доставки для первого окна
увеличится до 133 мс, а для всего объёма данных - более 1000 мс.

Для передачи пакетов в глобальной компьютерной сети используются специальные устройства - маршрутизаторы. Они подключены к нескольким линиям связи и на основе содержащихся в их памяти таблиц маршрутизации определяют, по какому из направлений передавать приходящие пакеты.
IPv4 - 4-я и первая, получившая широкое распространение, версия протокола IP (Internet Protocol).
Адреса в этой версии представляют собой 4 октета - блока по 8 бит. В человекочитаемом представлении адреса принято записывать в форме 4-х десятичных чисел от 0 до 255, разделённых точками.
Поскольку маршрутизатор имеет несколько интерфейсов (физических разъёмов, куда подключены кабели связи), в таблице маршрутизации задано соответствие каждого интерфейса той или иной сети. Сеть определяется парой из IP-адреса и битовой маски (в которой N старших бит заполнены единицами, а 32-N младших заполнены нулями). Для проверки того, можно ли маршрутизировать
пакет в какую-либо сеть, битовая маска применяется к адресу сети и адресу узла назначения из пакета с помощью побитового И. Если получившийся результат совпадает, то пакет можно отправить на соответствующий интерфейс.
Протокол управления передачей TCP (transmission control protocol) - протокол более высокого уровня по сравнению с IP, предназначенный для доставки данных в неизменном виде. Для решения этой задачи в нём применяется ряд принципов, один из которых - подтверждение
получения данных. Для подтверждения от получателя к отправителю направляется специальный пакет с признаком ACK, в котором указан диапазон полученных байтов.
При этом для исключения перегрузок сети при передаче больших объёмов данных применяются "окна" передачи. Окном называется максимальный объём данных, который может быть отправлен от отправителя получателю без подтверждения получения. По мере подтверждения получения данных окно смещается вправо и отправляются новые данные.

Входные данные
В первой строке записано натуральное число N, не превышающее 100 - количество маршрутизаторов. Далее записано N таблиц маршрутизации в следующем формате: в первой строке число N1 - количество маршрутов в таблице, далее N1 строк, где через пробел
указаны адрес сети, маска (целое число от 1 до 32), номер маршрутизатора, куда будет отправлен пакет (номера считаются с 1 по порядку описания), и время передачи до следующего маршрутизатора в миллисекундах.
После описания таблиц маршрутизации в следующей строке записаны через пробел адрес узла-отправителя, номер маршрутизатора, к которому он подключён, адрес узла-получателя, номер маршрутизатора, к которому подключён получатель, и объём данных (в байтах), который требуется передать.

Выходные данные
Минимальное время передачи в миллисекундах.
Примечание: считать, что между получением каждого пакета и отправкой подтверждения с конечного устройства всегда проходит 1 мс.
В рамках данной задачи считать, что потери отсутствуют и все отправленные пакеты достигают получателя, а также что размер окна фиксированный и составляет 10240 байт. Также следует пренебречь временем передачи данных между конечными узлами и ближайшими
маршрутизаторами.

Примечание
102400 = 10240*10, значит, для передачи данных потребуется 10 итераций (сдвигов окна передачи). Каждые 10 Кбайт будут проходить следующую цепочку: отправка с первого маршрутизатора на второй - 10мс, затем со 2-го на 4-й ещё 10 мс, затем 1 мс задержки на
отправку подтверждения и сама передача подтверждения напрямую с 4-го маршрутизатора на 1-й - ещё 10 мс. Таким образом, на передачу каждых 10 Кбайт будет уходить 31 мс.
 

Миссия космолёта “Юрий Гагарин” определена - посещение трех звёздных систем в глубоком космосе. Эти звёзды находятся на Земном небосводе в созвездии Орион:

•  звезда Беллатрикс (250 световых лет от Земли)
•  звезда Бетельгейзе (643 световых года от Земли)
•  парная звёздная система Ригель (773 световых года от Земли)

Маршрут путешествия должен предусматривать посещение их в порядке удаления от Земли. Однако гиперсветовой прыжок не может пока быть выполнен с приемлемой точностью на расстояние 20 и более световых лет. Спланированная трасса полёта должна состоять из серии
прыжков, каждый прыжок менее безопасного расстояния. Вторым ограничением является то, что промежуточные точки трассы должны находиться в окрестности массивного тела, т.е. звезды. Такие звёзды в навигации называются контрольными пунктами.
Необходимо учитывать, что управление выходом из гиперпространства невозможно без существенного искривления его в точке назначения гравитационным воздействием звезды контрольного пункта. Эта особенность налагает дополнительное ограничение на каждый
выполняемый гиперпрыжок: траектория прыжка не должна проходить меньше одного светового года от звёздной системы, не являющейся контрольным пунктом.
Задача : построить трассу в трёхмерном пространстве с минимально возможным количеством гиперпрыжков, при соблюдении указанных выше ограничений. Если таких трасс несколько, то следует выбрать ту, в которой суммарная длина трассы меньше.

Входные данные
Первая строка : натуральное число N - количество звезд, внесённых в лоцию (от 3 до 100).
Далее N строк, каждая содержит три целых числа, записанных через пробел: координаты X Y Z, заданные в световых годах. Все значения координат не превышают 10000. Точка старта (0 0 0) - звезда Солнце - не указана в лоции.
Три посещаемые звёздные системы находятся в лоции в порядке ожидаемого посещения, в строках с номерами 1, 2 и 3.

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

 

Примеры

№	Входные данные	Выходные данные
1	3 10 10 10 20 20 20 30 30 30	3 51.962 1 2 3
2	5 20 0 0 10 0 0 40 0 0 30 0 0 50 0 0	4 40.000 2 1 4 3

Примеры
Ввод