시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 19 14 13 81.250%

문제

2010년 노원구에 여러 층으로 이루어진 다리를 놓기로 결정했고 실제 디자인까지 완성하였다. 하지만 당연한 소리일지 모르지만 교각 없이 다리가 공중에 떠있을 수는 없기에 적절히 교각을 설치해야한다.

교각 설치 규칙은 다음과 같다. 다리의 양 끝을 다른 다리 위나 혹은 바닥에 설치해야하고 가능한한 교각의 길이는 최소로 하고 싶다. 단 다리는 모두 수평으로 놓여있고 다리는 수직으로 세워야한다.

예는 위 그림과 같다. 왼쪽 그림은 디자인된 다리를 표시한 것이고 오른쪽 그림은 교각을 놓은 다리를 표시한 것이다. 그리고 교각의 총 길이는 14가 되는 것을 알 수 있다.

문제는 다리가 주어졌을 때 총 교각의 길이 합을 구하는 것이다.

입력

첫째 줄에 다리의 개수를 나타내는 정수 N(1≤N≤100)이 주어진다. 둘째줄부터 N+1번째 줄까지 각 줄에 다리의 위치를 나타내는 세 정수 Y, X1, X2가 주어지는 이는 (X1, Y)부터 (X2, Y)까지 다리가 놓여있다는 의미이다. 모든 좌표는 10000을 넘지않는 자연수이다. 그리고 바닥의 Y좌표는 0이라고 가정한다. (X2 > X1+1)

출력

첫째 줄에 교각 길이의 총 합을 출력한다.

예제 입력

3
1 5 10
3 1 5
5 3 7

예제 출력

14

힌트