Лети, лети, лепесток,
Через запад на восток,
Через север, через юг,
Возвращайся, сделав круг.
Лишь коснёшься ты земли
Быть по-моему вели.
© Цветик-семицветик.
Во время осенних каникул, проходящих с 1 ноября по 8 ноября 2022 года, вы планируете совершить экскурсию в один из городов России. Вы даже выбрали город и даты полётов туда и обратно, но страница с результатами прогрузилась лишь частично. Вам требуется по имеющейся информации найти самый дешёвый вариант посетить выбранный город и вернуться, заодно посчитав, сколько у вас будет времени на осмотр достопримечательностей. Стоит учесть, что часто авиакомпании предоставляют скидку на перелёт туда-обратно.
Входные данные
В первой строке входного файла заданы два целых числа n и m — количество вариантов перелёта «туда» и «обратно» (1 <= n,m <= 1000). В следующих n строках описаны варианты перелёта «туда» в формате:
CCxxxx yyyy.mm.dd hh:mm YYYY.MM.DD HH:MM TT:tt value, где:
•
CC — код авиакомпании,
xxxx — номер рейса,
•
yyyy.mm.dd hh:mm — дата и время вылета,
•
YYYY.MM.DD HH:MM — дата и время прилёта,
•
TT:tt — время в пути, гарантируется, что время перелёта не превышает 24 часа,
•
value — целое число, стоимость перелёта (0 <= value <= 100000).
В следующих m строках описаны варианты перелёта «обратно» в том же формате. Дата вылета рейса «туда» во всех случаях как минимум на три дня раньше даты рейса «обратно».
Гарантируется, что все перелёты начинаются во время осенних каникул.
В последующих строках выписаны скидки, которые предоставляют авиакомпании за полёт тудаобратно. Каждая строка описывает одну авиакомпанию в формате: CC — код авиакомпании и value — целое число, размер скидки в процентах (0 <= value <= 100). Скидка рассчитывается с точностью до рублей, копейки отбрасываются в пользу клиента. Гарантируется, что у перечисленных компаний есть хотя бы один рейс либо «туда», либо «обратно», и что компании в данном списке не повторяются.
Выходные данные
В первой строке выведите два натуральных числа через пробел — оптимальные номера вариантов рейсов туда и обратно. Если существует несколько пар рейсов, дающих оптимальную стоимость, то нужно выбрать ту, которая позволяет провести за осмотром достопримечательностей как можно больше времени. Из всех таких пар выбрать ту, номера вариантов которой как можно раньше встретились в поисковой выдаче. Во второй строке выведите, сколько времени у вас будет на осмотр, в формате dd:hh:mm. Считается, что осмотр достопримечательностей начинается с момента прибытия и продолжается до момента отлёта.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 3
DP4160 2022.11.02 07:05 2022.11.02 07:35 02:35 4000
DP4130 2022.11.02 07:45 2022.11.02 08:10 02:36 3423
S71141 2022.11.07 05:55 2022.11.07 09:55 02:40 3432
S71042 2022.11.07 05:59 2022.11.07 09:59 02:45 3422
S71243 2022.11.07 04:25 2022.11.07 09:25 02:30 3432
DP 15
S7 10 |
2 2
04:21:49 |
Замечание
Россия – большая страна с 11 часовыми поясами, поэтому, вполне возможно прилететь в город назначения раньше, чем вылетел, поскольку время отправления и прибытия самолетов всегда указывается по местному времени. Из Челябинска можно улететь в Калининград, с разницей -3 часа, или во Владивосток, с разницей +6 часов.