UVA1161 Objective: Berlin

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=246&page=show_problem&problem=3602 [PDF](https://uva.onlinejudge.org/external/11/p1161.pdf) The administration of a well-known football team has made a study about the lack of support in international away games. This study has concluded that the only reason for this lack of support is the difficulty in organizing the travel arrangements. To help solving this problem, the administration has asked you to build a program that computes the maximum number of people that can fly from a departure city to a destination city, using the available places in regular flights in a given day, and arriving at or before a given time. When traveling from one city to another, a person may make multiple transfers. Each transfer is, at least, $30$ minutes long, i.e., the departure time should be, at least $30$ minutes after the arrival time. Given a set of flights for a single day and the latest arrival time, your program should compute the maximum number of persons that can fly, directly or indirectly, from a departure city to a destination city, arriving at or before the latest arrival time.

**The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line.** The first line contains an integer (smaller or equal to $150$) indicating the number of cities that have flight connections. The second line contains a string indicating the city of departure. The third line contains a string indicating the destination city. The fourth line contains the latest arrival time, in the format $\text{HHMM}$, where $\text{HH}$ is the hour in the day (from $\text{00}$ to $\text{23}$) and $\text{MM}$ is the minute in the hour (from $\text{00}$ to $\text{59}$). The fifth line contains an integer $N$ (smaller or equal to $5000$), with the number of existing flights. Each of the following $N$ lines contains the info for each flight. Each such line contains two strings and three integers, separated by blank spaces, $O\ E\ C\ D \ A$, where $O$ and $E$ are, respectively, the origin and destination of a flight, $C$ is the number of available places in the flight (from $0$ to $300$), and $D$ and $A$ are the departure and arrival times in the previously defined format $\text{HHMM}$. All flights start and end in the same day. City names may have up to 8 characters.

**For each test case, the output must follow the description below.** The output consists of one single line with an integer stating the maximum number of people that can fly from the origin to the destination city, using the given flights and arriving at or before the given latest arrival time.

### Sample Input ```sample 4 lisbon berlin 1500 9 lisbon london 6 1000 1100 london lisbon 6 1130 1230 lisbon paris 5 1000 1100 paris lisbon 4 1130 1230 london paris 1 1130 1300 london berlin 2 1340 1510 berlin london 2 1300 1430 paris berlin 10 1330 1500 berlin paris 9 1300 1430 ``` ### Sample Output ```sample 6 ```