Automatic Fence Gate

Time limit1sMemory limit1024 MB

Summary

Given N timed commands to raise or lower a gate, listed out of order, find the total minutes the gate is fully closed when run in time order.

Level: Medium4 of 10
Topics: Sorting, Prefix sum, Simulation
Solved: No attempts yet

Problem

Farmer John (FJ) recently installed an electronic gate between his two fields. He can control the gate from his home computer by sending it commands such as "raise 10 inches" and "lower 5 inches".

The gate is considered open when it is raised as high as possible, and closed when it is lowered to ground level. FJ carefully planned the sequence of raising and lowering instructions for the day, but a lightning storm scrambled the contents of his computer. His list of $N$ ( $1 \le N \le 1000$ ) instructions now appears out of order, for example:

11:30pm raise the gate 5 inches
10:05am lower the gate 3 inches
12:03pm raise the gate 6 inches
04:01am lower the gate 2 inches
... and so on.

FJ planned to execute these instructions in chronological order, starting at midnight (12:00am) and ending at 11:59pm the same day. He remembers that his instructions would have caused the gate to completely close at least once. Determine the total number of minutes the gate would have been completely closed if he executed his instructions in the originally planned order.

Input

Line 1: The single integer $N$
Lines 2 to $N+1$ : Each line is one instruction with two space-separated fields. The first is a 7-digit timestamp in the form HH:MMxx, where HH is hours, MM is minutes, and xx is either am or pm. The second is an integer giving the number of inches to raise the gate. Negative numbers mean lowering the gate.

Output

Line 1: A single integer, the number of minutes during the day that the gate is completely closed.

Hint

At 1:00am the gate is raised 5 inches, at 1:30am it is lowered 10 inches, and at 1:30pm it is raised 1 inch. The gate is closed at some point, so the closed interval must be from 1:30am to 1:30pm. That lasts 12 hours (720 minutes).

Examples1

Example 1
Input
```
3
1:30pm 1
1:30am -10
1:00am 5
```
Expected output
```
720
```