사건은 다가와 (Hard)

시간 제한4초메모리 제한1024 MB

요약
수직선 위 원점에서 출발해 각 시각마다 주어진 위험 구간 밖에 있어야 할 때, 최소 이동 거리를 구하거나 불가능하면 -1을 출력한다.
난이도

보통10점 중 7점

유형
그리디, 구간, 정렬
정답자
아직 제출이 없습니다

문제

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

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

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

위치 AA와 위치 BB는 안전하다는 점에 유의하라.

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

입력

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

이후 NN개의 줄에, 각 사건의 TT, AA, BB가 공백을 사이에 두고 주어진다.

출력

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

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

제한

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤100,0001 \le N \le 100\\,000
  • 1≤T≤1,000,000,0001 \le T \le 1\\,000\\,000\\,000
  • −1,000,000,000≤A<B≤1,000,000,000-1\\,000\\,000\\,000 \le A < B \le 1\\,000\\,000\\,000
  • 각 사건의 TT는 모두 다르다.

예제3

  1. 예제 1

    입력
    3
10 -3 7
20 -8 2
25 3 9
    예상 출력
    8

  2. 예제 2

    입력
    3
3 -3 7
7 -8 2
8 3 9
    예상 출력
    -1

  3. 예제 3

    입력
    10
37 -8 16
38 -4 16
12 -42 -31
24 -9 11
16 -32 -14
26 1 18
11 -43 -40
18 -17 2
47 28 35
33 -50 -49
    예상 출력
    18