Under construction

Still being built. Things may change

Kansas

Time limit2sMemory limit1024 MB

Summary
Track the clock-bearing driving segments and rest breaks to count breaks before the path first crosses the start, or report -1.
Level

Medium5 of 10

Topics
Geometry, Simulation, Math
Solved
No attempts yet

Problem

The road map of Kansas is a grid. Straight roads run north to south and straight roads run east to west, each spaced 1 mile apart. A truck driver receives instructions in this form: drive north for two hours at 45 miles per hour, then west for five hours at 65 miles per hour.

The driver has to take a 1 hour break after every 5 hours of continuous driving. Those 5 hours carry over from one instruction to the next, because changing direction is not a rest. The driver does not move during a break.

Count how many breaks the driver has taken at the moment she first passes through or returns to the point she started from. If she reaches that point at the exact instant a break would begin, she reaches it first, so that break is not counted. The moment of departure itself does not count as passing through.

Input

The first line contains the number of instructions nn (1≤n≤10001 \le n \le 1000). Each of the next nn lines holds one instruction: the direction dd, the number of hours hh (1≤h≤2001 \le h \le 200), and the speed ss (1≤s≤2001 \le s \le 200) in miles per hour, in that order. hh and ss are integers.

The direction is written as the position of the hour hand on an analog clock. 12 is north, 6 is south, 9 is west, 3 is east.

Output

Print one integer, the number of breaks the driver took before she first passed through or returned to the starting point. If she never reaches it after following every instruction, print -1.

Examples3

  1. Example 1

    Input
    6
6 2 30
9 4 40
12 3 20
3 6 60
12 5 30
6 6 60
    Expected output
    2

  2. Example 2

    Input
    5
6 1 30
9 2 40
12 1 30
3 1 79
12 5 30
    Expected output
    -1

  3. Example 3

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