Minimum Travel Time with Bus Transfers

Mr. Malnar wishes to travel from Zagreb to Wrocław. However, there is no direct bus between these two cities, so he must take a bus from Zagreb to Graz and then transfer to a bus from Graz to Wrocław.

You are given a schedule of n daily bus trips. Each bus runs on a fixed route (either Zagreb-Graz or Graz-Wrocław) and has a departure time (the bus departs at the beginning of that minute) and an arrival time (the bus arrives at the end of that minute). Note that the transfer time is negligible, but the arrival time of the first bus must be strictly less than the departure time of the second bus in order to catch the connection.

Your task is to determine the minimum total travel time (in minutes) from Zagreb to Wrocław. The total travel time is calculated as the difference between the departure time of the first bus and the arrival time of the second bus. If it is not possible for Mr. Malnar to reach Wrocław using the available bus trips, output -1.

Note: If there is a valid transfer, let the first bus have departure time \(d_1\) and arrival time \(a_1\), and the second bus have departure time \(d_2\) and arrival time \(a_2\). The condition for a valid connection is:

\[ a_1 < d_2 \]

and the total travel time is \(a_2 - d_1\).

inputFormat

The first line contains an integer (n) (the number of bus trips). Each of the next (n) lines describes a bus trip in the format:

route departure_time arrival_time

where route is either "Zagreb-Graz" or "Graz-Wrocław", and departure_time and arrival_time are integers (minutes). Note that departure and arrival times are given in minutes, and the bus departs at the beginning of the departure minute and arrives at the end of the arrival minute.

outputFormat

Output a single integer representing the minimum total travel time from Zagreb to Wrocław. If it is impossible to catch a valid bus transfer, output -1.

sample

2
Zagreb-Graz 10 20
Graz-Wrocław 21 30

20