ACSL Practice 2009

The road map of Kansas is a grid where there are straight roads going North to South and straight roads East to West each ~1~ mile apart. A truck driver gets instructions in the following form: Drive for two hours north at ~50~ miles per hour, then for ~7~ hours east at ~85~ miles per hour, etc. The driver has to take a ~1~ hour break after ~5~ hours of driving. After how many breaks does the driver first pass through or return to the place where he started?

Example 1. Drive for two hours south at ~30~ miles per hour, then for ~4~ hours west at ~40~ miles per hour, then for ~3~ hours north at ~20~ miles per hour, then for ~6~ hours east at ~60~ miles per hour, then for ~5~ hours north at ~30~ miles per hour, and then for ~6~ hours south at ~60~ miles per hour.

When following these instructions, the driver will pass through his starting point after taking two breaks.

Example 2. Drive for ~1~ hour south at ~30~ miles per hour, then for ~2~ hours west at ~40~ miles per hour, then for ~1~ hour north at ~30~ miles per hour, then for ~1~ hour east at ~79~ miles per hour, and then for ~5~ hours north at ~30~ miles per hour.

When following these instructions, the driver will not pass through nor return to where he started.

Example 3. Drive for four hours west at ~60~ miles per hour, then drive for eight hours north at ~80~ miles per hour, then drive for four hours east at ~60~ miles per hour, then drive for eight hours south at ~100~ miles per hour, then drive for ten hours east at ~20~ miles per hour.

When following these instructions, the driver will pass through his starting point after taking ~4~ breaks.

Input Specification

The input consists of several lines. The first line contains an integer ~(N \le 1\,000)~ which is the number of instructions, followed by one line for each instruction, indicating the direction, the number of hours ~h~ ~(1 \le h \le 200)~ and the speed ~s~ ~(1 \le s \le 200)~ in miles per hour in this order. The geographical directions are indicated by the position of the small hand on an analog clock; ~12~ stands for north, ~6~ for south, ~9~ for west, and ~3~ for east.

Output Specification

The output contains a single integer which is the number of breaks taken before the driver first passes through or returns to the place where he started. If the driver does not reach or pass through the place where he started after following all instructions, the output should contain the number -1.

Sample Input 1

6
6 2 30
9 4 40
12 3 20
3 6 60
12 5 30
6 6 60

Sample Output 1

2

Sample Input 2

5
6 1 30
9 2 40
12 1 30
3 1 79
12 5 30

Sample Output 2

-1

Sample Input 3

5
9 4 60
12 8 80
3 4 60
6 8 100
3 10 20

Sample Output 3

4