사건은 다가와 (Hard)

민정이는 현재 수직선의 원점(위치 0)에 있다. 민정이는 매 시점 수직선 위에서 왼쪽 또는 오른쪽으로 1초에 1의 속도로 이동할 수 있다. 물론, 정지해 있을 수도 있다.

민정이는 다음과 같은 사건이 $N$번 발생할 것이라는 걸 알고 있다.

• $T$초 뒤에 민정이가 위치 $A$ 초과 위치 $B$ 미만에 있으면, 카리나의 body bang을 맞게 된다.

위치 $A$와 위치 $B$는 안전하다는 점에 유의하라.

민정이는 카리나의 body bang을 맞지 않도록 적절히 움직이려 한다. 민정이가 움직여서 카리나의 body bang을 피할 수 있는지 판별하고, 피할 수 있다면 이동 거리를 최소화하라.

첫째 줄에, 사건이 발생하는 횟수 $N$이 주어진다.

이후 $N$개의 줄에, 각 사건의 $T$, $A$, $B$가 공백을 사이에 두고 주어진다.

민정이가 카리나의 body bang을 피할 수 없다면, -1을 출력한다.

민정이가 카리나의 body bang을 피할 수 있다면, 민정이의 최소 이동 거리를 출력한다.

• 주어지는 모든 수는 정수이다.
• $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$
• 각 사건의 $T$는 모두 다르다.