Fly, fly, petal,
Through the west to the east,
Through the north, through the south,
Come back around.
As soon as you touch the ground
Be led in my opinion.
© Flower-seven-flower.
During the autumn holidays from November 1 to November 8, 2022, you are planning to make an excursion to one of the Russian cities. You even selected a city and dates for round trip flights, but the results page only partially loaded. You need to find the cheapest option to visit the selected city according to the available information and return, at the same time considering how much time you will have for sightseeing. It is worth considering that airlines often provide a discount for a round-trip flight.
Input
The first line of the input file contains two integers n and m — number of flight options «there» and "back" (1 <= n, m <= 1000). The next n lines describe the flight options "there" in the format:
CCxxxx yyyy.mm.dd hh:mm YYYY.MM.DD HH:MM TT:tt value, where:
CC— airline code,
xxxx — flight number,
yyyy.mm.dd hh:mm — date and time of departure,
YYYY.MM.DD HH:MM — date and time of arrival,
TT:tt — travel time, it is guaranteed that the flight time does not exceed 24 hours,
value— integer, flight cost (0 <= value <= 100000).
The next m lines describe the options for the flight "back" in the same format. Departure date of the outbound flight in all cases at least three days before the date of the "return" flight.
It is guaranteed that all flights start during the autumn holidays.
In the following lines, the discounts provided by the airlines for the round-trip flight are written out. Each line describes one airline in the format: CC — airline code and value — integer, discount amount in percent (0 <= value <= 100). The discount is calculated to the nearest roubles, pennies are discarded in favor of the client. It is guaranteed that the listed companies have at least one flight either "there" or "back", and that the companies in this list do not repeat.
Imprint
In the first line print two space-separated natural numbers — optimal numbers of round-trip flight options. If there are several pairs of flights that give the best cost, then you need to choose the one that allows you to spend as much time sightseeing as possible. Of all such pairs, choose the one whose options numbers were found in the search results as early as possible. In the second line print how much time you will have for inspection, in the format dd:hh:mm. It is considered that sightseeing begins from the moment of arrival and continues until the moment of departure.
Examples
| # |
Input |
Output |
| 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 |
Remark
Russia – a large country with 11 time zones, therefore, it is quite possible to arrive at the destination city earlier than the departure, since the departure and arrival times of the aircraft are always indicated in local time. From Chelyabinsk you can fly to Kaliningrad, with a difference of -3 hours, or to Vladivostok, with a difference of +6 hours.