21656번 - Почта 스페셜 저지다국어

В городе π планируется проведение реформы доставки почты. Вместо большого количества устаревших автомобилей приобретён специализированный Е-мобиль, задача которого — развозить всю корреспонденцию по почтовым отделениям города.

IT-отдел городской почты разработал кольцевой маршрут, проходящий через все почтовые отделения. Все улицы в городе  с односторонним движением. Необходимо выбрать почтовое отделение для размещения логистического центра, куда будет поступать вся городская корреспонденция перед её отправкой на Е-мобиле по маршруту. Из-за пробок скорость движения на участках маршрута между почтовыми отделениями зависит от времени суток. Размещение логистического центра считается оптимальным, если после отъезда из него в нулевой момент времени Е-мобиль развезёт корреспонденцию и возвратится в логистический центр как можно раньше. Время разгрузки корреспонденции пренебрежимо мало.

Требуется написать программу, которая по заданному маршруту с учетом скорости движения Е-мобиля определяет оптимальное расположение логистического центра и наиболее ранний возможный момент возврата в логистический центр.

В первой строке задаётся целое положительное число N  — количество почтовых отделений в городе π. Почтовые отделения нумеруются в порядке их следования по маршруту, начиная с единицы.

В следующих строках описаны N участков маршрута между почтовыми отделениями. Каждое описание содержит три строки:

• в первой строке описания задаётся целое положительное число d_i  — длина данного участка (d_i ≤ 10⁹), а также целое неотрицательное число E_i  — количество отрезков времени, в течение каждого из которых скорость движения Е-мобиля постоянна;
• во второй строке даны целые положительные числа t_i,j (1 ≤ j ≤ E_i, 0 < t_i,1 < … < t_i,Ei ≤ 10⁹) — значения моментов времени, в которые изменяется скорость движения. Если соответствующее E_i равно нулю, то эта строка — пустая;
• в третьей строке целые положительные числа v_j – скорости на полуинтервале времени [t_i,j-1, t_i,j), где 1 ≤ j ≤ E_i+1, считается, что t_i,0 = 0, t_i,Ei+1 = +∞.

Все числа в строках разделяются одним пробелом.

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

Ответ должен иметь абсолютную или относительную погрешность не более 10^-9, что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно x, а в правильном ответе оно равно y. Ответ будет засчитан, если значение выражения |x – y| / max{1, | y| }; не превышает 10^-9.

В тестах третьего набора количество почтовых отделений N ≤ 10⁵, N ≤ ΣE_i ≤ 3·10⁵. Каждый тест для третьей подзадачи оценивается отдельно.