만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

사건은 다가와 (Easy)

면접 대비

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

요약
시각 T마다 A와 B 사이(A, B 제외)에 있으면 안 되는 민정이가 0에서 출발해 이동 거리를 최소로 하는 값을 구하는 문제입니다.
난이도

쉬움10점 중 3점

유형
동적 계획법, 시뮬레이션
정답자
아직 제출이 없습니다

문제

민정이는 현재 수직선의 원점(위치 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≤1001 \le N \le 100
  • 1≤T≤1 0001 \le T \le 1\,000
  • −1 000≤A<B≤1 000-1\,000 \le A < B \le 1\,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