Events are coming (Easy)

Interview

Time limit1sMemory limit1024 MB

Summary

Given times T with forbidden open intervals (A, B), find the minimum distance Minjeong walks from 0 at speed at most 1 to avoid them, or report -1.

Level: Easy3 of 10
Topics: Dynamic programming, Simulation
Solved: No attempts yet

Problem

Minjeong is currently at the origin (position 0) of the number line. At any moment, Minjeong can move left or right along the number line at a speed of 1 unit per second. Of course, Minjeong may also stay still.

Minjeong knows that the following event will occur $N$ times.

If Minjeong is strictly between position $A$ and position $B$ after $T$ seconds, Minjeong will be hit by Karina's body bang.

Positions $A$ and $B$ are safe.

Minjeong wants to move appropriately so as not to be hit by Karina's body bang. Determine whether Minjeong can avoid the body bang by moving, and if so, minimize the travel distance.

Input

The first line contains the number of events $N$ .

Each of the next $N$ lines contains $T$ , $A$ , and $B$ for one event, separated by spaces.

Output

If Minjeong cannot avoid Karina's body bang, print -1.

If Minjeong can avoid Karina's body bang, print the minimum travel distance of Minjeong.

Constraints

All given numbers are integers.
$1 \le N \le 100$
$1 \le T \le 1\,000$
$-1\,000 \le A < B \le 1\,000$
The $T$ of each event is distinct.

Examples3

Example 1
Input
```
3
10 -3 7
20 -8 2
25 3 9
```
Expected output
```
8
```
Example 2
Input
```
3
3 -3 7
7 -8 2
8 3 9
```
Expected output
```
-1
```

Example 3

Input

Expected output