Events Are Approaching (Hard)

Time limit4sMemory limit1024 MB

Summary

Given N timed events that forbid positions strictly between A and B at each time T, find the minimum total distance Minjeong moves to dodge them all, or -1 if impossible.

Level: Hard8 of 10
Topics: Dynamic programming, Intervals, Sorting
Solved: No attempts yet

Problem

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

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

If Minjeong is at a position strictly greater than $A$ and strictly less than $B$ after $T$ seconds, Minjeong gets hit by Karina's body bang.

Positions $A$ and $B$ are safe.

Minjeong wants to move so as to avoid Karina's body bang. Determine whether Minjeong can avoid it by moving, and if so, minimize the total distance moved.

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 it, print the minimum distance Minjeong must move.

Constraints

All given numbers are integers.
$1 \le N \le 100\,000$
$1 \le T \le 1\,000\,000\,000$
$-1\,000\,000\,000 \le A < B \le 1\,000\,000\,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