시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 57 25 24 44.444%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

3
1 5 10
3 1 5
5 3 7

예제 출력 1

14

힌트

W3sicHJvYmxlbV9pZCI6IjEyNzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNTBcdWFjMDEgXHViMTkzXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD4yMDEwXHViMTQ0IFx1YjE3OFx1YzZkMFx1YWQ2Y1x1YzVkMCBcdWM1ZWNcdWI3ZWMgXHVjZTM1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWIyZTRcdWI5YWNcdWI5N2MgXHViMTkzXHVhZTMwXHViODVjIFx1YWNiMFx1YzgxNVx1ZDU4OFx1YWNlMCBcdWMyZTRcdWM4MWMgXHViNTE0XHVjNzkwXHVjNzc4XHVhZTRjXHVjOWMwIFx1YzY0NFx1YzEzMVx1ZDU1OFx1YzYwMFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YjJmOVx1YzVmMFx1ZDU1YyBcdWMxOGNcdWI5YWNcdWM3N2NcdWM5YzAgXHViYWE4XHViOTc0XHVjOWMwXHViOWNjIFx1YWQ1MFx1YWMwMSBcdWM1YzZcdWM3NzQgXHViMmU0XHViOWFjXHVhYzAwIFx1YWNmNVx1YzkxMVx1YzVkMCBcdWI1YTBcdWM3ODhcdWM3NDQgXHVjMjE4XHViMjk0IFx1YzVjNlx1YWUzMFx1YzVkMCBcdWM4MDFcdWM4MDhcdWQ3ODggXHVhZDUwXHVhYzAxXHVjNzQ0IFx1YzEyNFx1Y2U1OFx1ZDU3NFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZDUwXHVhYzAxIFx1YzEyNFx1Y2U1OCBcdWFkZGNcdWNlNTlcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC4gXHViMmU0XHViOWFjXHVjNzU4IFx1YzU5MSBcdWIwNWRcdWM3NDQgXHViMmU0XHViOTc4IFx1YjJlNFx1YjlhYyBcdWM3MDRcdWIwOTggXHVkNjM5XHVjNzQwIFx1YmMxNFx1YjJlNVx1YzVkMCBcdWMxMjRcdWNlNThcdWQ1NzRcdWM1N2NcdWQ1NThcdWFjZTAgXHVhYzAwXHViMmE1XHVkNTVjXHVkNTVjIFx1YWQ1MFx1YWMwMVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuIFx1YjJlOCBcdWIyZTRcdWI5YWNcdWIyOTQgXHViYWE4XHViNDUwIFx1YzIxOFx1ZDNjOVx1YzczY1x1Yjg1YyBcdWIxOTNcdWM1ZWNcdWM3ODhcdWFjZTAgXHViMmU0XHViOWFjXHViMjk0IFx1YzIxOFx1YzljMVx1YzczY1x1Yjg1YyBcdWMxMzhcdWM2Y2NcdWM1N2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcLzIwMTAwNFwvbm93b24uSlBHXCIgc3R5bGU9XCJoZWlnaHQ6MzI2cHg7IHdpZHRoOjkzM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1YjI5NCBcdWM3MDQgXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1YjJlNC4gXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc0MCBcdWI1MTRcdWM3OTBcdWM3NzhcdWI0MWMgXHViMmU0XHViOWFjXHViOTdjIFx1ZDQ1Y1x1YzJkY1x1ZDU1YyBcdWFjODNcdWM3NzRcdWFjZTAgXHVjNjI0XHViOTc4XHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc0MCBcdWFkNTBcdWFjMDFcdWM3NDQgXHViMTkzXHVjNzQwIFx1YjJlNFx1YjlhY1x1Yjk3YyBcdWQ0NWNcdWMyZGNcdWQ1NWMgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhZDUwXHVhYzAxXHVjNzU4IFx1Y2QxZCBcdWFlMzhcdWM3NzRcdWIyOTQgMTRcdWFjMDAgXHViNDE4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjODFjXHViMjk0IFx1YjJlNFx1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjIFx1Y2QxZCBcdWFkNTBcdWFjMDFcdWM3NTggXHVhZTM4XHVjNzc0IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjJlNFx1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCBOKDEmbGU7TiZsZTsxMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4XHVjOTA0XHViZDgwXHVkMTMwIE4rMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgXHVhYzAxIFx1YzkwNFx1YzVkMCBcdWIyZTRcdWI5YWNcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMxMzggXHVjODE1XHVjMjE4IFksIFgxLCBYMlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjNzc0XHViMjk0IChYMSwgWSlcdWJkODBcdWQxMzAgKFgyLCBZKVx1YWU0Y1x1YzljMCBcdWIyZTRcdWI5YWNcdWFjMDAgXHViMTkzXHVjNWVjXHVjNzg4XHViMmU0XHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAxMDAwMFx1Yzc0NCBcdWIxMThcdWM5YzBcdWM1NGFcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViYzE0XHViMmU1XHVjNzU4IFlcdWM4OGNcdWQ0NWNcdWIyOTQgMFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NWNcdWIyZTQuIChYMiAmZ3Q7IFgxKzEpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFkNTBcdWFjMDEgXHVhZTM4XHVjNzc0XHVjNzU4IFx1Y2QxZCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEyNzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQTEFURk9STUUiLCJkZXNjcmlwdGlvbiI6IjxwPkEgbGV2ZWwgaXMgYmVpbmcgZGVzaWduZWQgZm9yIGEgbmV3IHBsYXRmb3JtIGdhbWUuIFRoZSBsb2NhdGlvbnMgb2YgdGhlIHBsYXRmb3JtcyBoYXZlIGJlZW4gY2hvc2VuLiBDb250cmFyeSB0byBwb3B1bGFyIG9waW5pb24sIHBsYXRmb3JtcyBjYW4mIzM5O3QgZmxvYXQgaW4gdGhlIGFpciwgYnV0IG5lZWQgcGlsbGFycyBmb3Igc3VwcG9ydC4gTW9yZSBwcmVjaXNlbHksIGVhY2ggb2YgdGhlIHR3byBlbmRzIG9mIHRoZSBwbGF0Zm9ybSBuZWVkcyB0byBiZSBzdXBwb3J0ZWQgYnkgYSBwaWxsYXIgc3RhbmRpbmcgb24gdGhlIGZsb29yIG9yIG9uIGEgZGlmZmVyZW50IHBsYXRmb3JtLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3Ugd2lsbCBiZSBnaXZlbiB0aGUgbG9jYXRpb25zIG9mIHRoZSBwbGF0Zm9ybXMgaW4gYSBjb29yZGluYXRlIHN5c3RlbSBhcyBpbiB0aGUgbGVmdCBpbWFnZSBiZWxvdy4gRWFjaCBwbGF0Zm9ybSYjMzk7cyBsb2NhdGlvbiBpcyBkZXRlcm1pbmVkIGJ5IGl0cyBhbHRpdHVkZSAodmVydGljYWwgZGlzdGFuY2UgZnJvbSB0aGUgZ3JvdW5kKSBhbmQgdGhlIHN0YXJ0IGFuZCBlbmQgY29vcmRpbmF0ZXMgaW4gdGhlIGhvcml6b250YWwgZGlyZWN0aW9uLiBFYWNoIHN1cHBvcnQgcGlsbGFyIGlzIHBsYWNlZCBoYWxmIGEgdW5pdCBmcm9tIHRoZSBlbmQgb2YgYSBwbGF0Zm9ybSwgYXMgaW4gdGhlIHJpZ2h0IGltYWdlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5EZXRlcm1pbmUgdGhlIHRvdGFsIGxlbmd0aCBvZiBwaWxsYXJzIG5lZWRlZCB0byBzdXBwb3J0IGFsbCB0aGUgcGxhdGZvcm1zLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BsYXRmb3JtLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI1MHB4OyB3aWR0aDo2MjdweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgTiwgMSAmbGU7IE4gJmxlOyAxMDAsIHRoZSBudW1iZXIgb2YgcGxhdGZvcm1zLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0aGUgcG9zaXRpb24gb2Ygb25lIHBsYXRmb3JtLCB0aHJlZSBjb29yZGluYXRlcyBZLCBYPHN1Yj4xPFwvc3ViPiBhbmQgWDxzdWI+MjxcL3N1Yj4uJm5ic3A7PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPlRoZSBmaXJzdCBudW1iZXIgaXMgdGhlIGFsdGl0dWRlLCB0aGUgb3RoZXIgdHdvIHRoZSBob3Jpem9udGFsIGNvb3JkaW5hdGVzLiBBbGwgY29vcmRpbmF0ZXMgd2lsbCBiZSBwb3NpdGl2ZSBpbnRlZ2VycyBsZXNzIHRoYW4gMTAwMDAgc2F0aXNmeWluZyBYPHN1Yj4yPFwvc3ViPiAmZ3Q7IFg8c3ViPjE8XC9zdWI+KzEgKGkuZS4gdGhlIGxlbmd0aCBvZiBlYWNoIHBsYXRmb3JtIHdpbGwgYmUgYXQgbGVhc3QgMikuJm5ic3A7PFwvc3Bhbj48XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IHdpbGwgYmUgc3VjaCB0aGF0IG5vIHR3byBwbGF0Zm9ybXMgb3ZlcmxhcC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHRvdGFsIGxlbmd0aCBvZiBwaWxsYXJzIG5lZWRlZCB0byBzdXBwb3J0IGFsbCB0aGUgcGxhdGZvcm1zLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=