시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB95555.556%

문제

The road map of Kansas, USA, is a grid where there are straight roads North-South and straight roads East-West each 1 mile apart.  A truck driver gets instructions in the following form.  Drive for two hours north at 45 miles per hour, then for 5 hours west at 65 miles per hour, etc.  The driver will have to take a break of 1 hour after 5 hours of continuous driving.  The aim is to compute, after how many breaks the driver for the first time passes through or finally returns to the place where she started from.

입력

The first line contains an integer (≤ 1000) which is the number of instructions, followed by one line for each instruction, indicating the direction, the number of hours h (1 ≤ h ≤ 200) and the speed s (1 ≤ s ≤ 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.

출력

The output contains an integer which is the number of breaks taken before the driver for the first time passes through or finally returns to the place where she started from.  If the driver does not reach or pass through the place where she started from after following all instructions, the output file should contain the number -1.

예제 입력 1

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

예제 출력 1

2

예제 입력 2

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

예제 출력 2

-1

예제 입력 3

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

예제 출력 3

4

힌트

Example 1.  Drive for two hours south at 30 miles per hour, then for four hours west at 40 miles per hour, then for three hours north at 20 miles per hour, then for six hours east at 60 miles per hour, then for five hours north at 30 miles per hour, and then for six hours south at 60 miles per hour.

When following these instructions, the driver will be passing through where she started from after taking two breaks.

Example 2.  Drive for one hour south at 30 miles per hour, then for two hours west at 40 miles per hour, then for one hour north at 30 miles per hour, then for one hour east at 79 miles per hour, and then for five hours north at 30 miles per hour.

When following these instructions, the driver will neither pass through nor be back where she started from.

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 where she started from after taking 4 breaks.