Traffic Lights#175
An emergency vehicle needs to travel from one intersection to another in the city. What is the minimum time required to reach the destination if the vehicle has a complete city map with all traffic light schedules and can travel at the maximum allowed speed of km/h along the optimal route?
The city map is a rectangle of size N \times M km (1 \leq N, M \leq 25). The city has M + 1 streets running parallel from north to south and N + 1 avenues running parallel from west to east. The distance between neighboring streets or avenues is meters.
By convention, streets are numbered from west to east by consecutive natural numbers starting at . Avenues are designated from north to south by consecutive Latin letters starting with . Thus, each intersection can be uniquely identified by a pair consisting of a letter and a number, for example, .
Each intersection may have a traffic light. For the -th traffic light, an integer K_i (1 \leq K_i \leq 180) is known, defining its cycle: for flows moving from west and east, the green light is on for (K_i - 1) seconds, then yellow for second, then red for K_i seconds; for flows moving from north and south, red is on for K_i seconds, then green for (K_i - 1) seconds, then yellow for second. You are allowed to go straight or turn at both the green and yellow lights. At the starting moment, each traffic light is D_i seconds into its cycle (D_i is an integer, 0 \leq D_i < 2K_i).
The first line contains two integers and separated by a space.
The second line contains the designations of the starting and ending intersections, separated by a space.
The third line contains a single integer , the number of traffic lights, where 0 \leq K \leq (N + 1)(M + 1).
The next lines each contain the intersection label, followed by the integers K_i and D_i, separated by spaces.
Output a single integer: the minimal time in seconds required to travel from the starting intersection to the destination intersection.
Example 1