Calculating Taxi Fare

Time limit1sMemory limit128 MB

Summary

Given a sequence of streets with lengths and per-kilometer times, compute a passenger's fare between two streets using tiered per-kilometer pricing plus night and traffic surcharges.

Level: Medium7 of 10
Topics: Simulation, Implementation, Math, Prefix sum
Solved: No attempts yet

Problem

Taxi fares are complicated: they depend on how far you travel, the time of day, and the traffic. A taxi drives through a sequence of streets $S_1, S_2, \dots, S_n$ in this exact order. Street $S_i$ is $L_i$ kilometers long, and the taxi keeps a constant speed on it, taking $M_i$ minutes to drive one kilometer of $S_i$ .

A passenger boards at the start of some street $S_i$ and gets off at the end of a later street $S_j$ (boarding and alighting always happen at a street's end, never in the middle of a street). The passenger is charged per kilometer:

Each of the first 10 kilometers costs 1000 Rials.
Each of the next 20 kilometers (kilometers 11 through 30) costs 250 Rials.
Each kilometer after the 30th costs 100 Rials.

Two surcharges may then apply:

Night surcharge. Consider each kilometer separately. If the taxi spends at least one minute driving that kilometer during the interval from 12:00 AM to 6:00 AM, that kilometer costs 20% more.
Traffic surcharge. If the average speed over the whole trip is less than 30 km/h, the fare is increased by 10%.

The night surcharge is added per kilometer first; the 10% traffic surcharge is then applied once to the resulting total.

Input

The input contains several test cases. Each test case has two parts.

The first part lists the streets the taxi drives through, one per line and in travel order:

street-name length min

Here street-name is a unique string of at most 20 letters and digits with no spaces, length is $L_i$ in kilometers (at most 200), and min is $M_i$ in minutes; both are positive integers. Each street is visited exactly once. This part ends with a line containing only a single $ character.

The second part is one line:

source-street dest-street time

source-street and dest-street are the boarding and alighting street names, and time is the boarding time in 24-hour HH:MM format. Both streets belong to the street list, and the destination street does not come before the source street. A line containing only a single # character ends each test case.

The input ends with a line containing two dash characters --.

Output

For each test case, print a single line containing the fare of the passenger's trip.

Examples8

Example 1

Input

Khayyam 10 35
15thKhordad 50 15 
Pamenar 15 40
$
Khayyam Pamenar 07:15
#
Jenah 10 40
Nouri 50 70
Hemmat 30 25
Chamran 80 80
ValieAsr 30 20
$
Nouri ValieAsr 23:30
#
--

Expected output

21758
36432

Example 2
Input
```
Main 5 1
$
Main Main 10:00
#
--
```
Expected output
```
5000
```
Example 3
Input
```
Ave 40 1
$
Ave Ave 09:00
#
--
```
Expected output
```
16000
```
Example 4
Input
```
Dark 5 10
$
Dark Dark 02:00
#
--
```
Expected output
```
6600
```

Example 5

Input

Long 20 20
$
Long Long 23:00
#
--

Expected output

Example 6

Input

X 3 5
$
X X 12:00
#
Y 12 2
$
Y Y 12:00
#
--

Expected output

3300
10500

Example 7

Input

A 5 1
B 10 3
C 8 3
D 20 1
$
B C 14:00
#
--

Expected output

Example 8
Input
```
Road 30 2
$
Road Road 08:00
#
--
```
Expected output
```
15000
```