시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 67 31 30 46.875%

문제

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+XHJcblxyXG5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjJlNFx1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCBOKDEmbGU7TiZsZTsxMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIFx1YWMwMSBcdWM5MDRcdWM1ZDAgXHViMmU0XHViOWFjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCBZLCBYMSwgWDJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1Yzc3NFx1YjI5NCAoWDEsIFkpXHViZDgwXHVkMTMwIChYMiwgWSlcdWFlNGNcdWM5YzAgXHViMmU0XHViOWFjXHVhYzAwIFx1YjE5M1x1YzVlY1x1Yzc4OFx1YjJlNFx1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM4OGNcdWQ0NWNcdWIyOTQgMTAwMDBcdWM3NDQgXHViMTE4XHVjOWMwXHVjNTRhXHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YmMxNFx1YjJlNVx1Yzc1OCBZXHVjODhjXHVkNDVjXHViMjk0IDBcdWM3NzRcdWI3N2NcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LiAoWDIgJmd0OyBYMSsxKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZDUwXHVhYzAxIFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWNkMWQgXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMjc2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUExBVEZPUk1FIiwiZGVzY3JpcHRpb24iOiI8cD5BIGxldmVsIGlzIGJlaW5nIGRlc2lnbmVkIGZvciBhIG5ldyBwbGF0Zm9ybSBnYW1lLiBUaGUgbG9jYXRpb25zIG9mIHRoZSBwbGF0Zm9ybXMgaGF2ZSBiZWVuIGNob3Nlbi4gQ29udHJhcnkgdG8gcG9wdWxhciBvcGluaW9uLCBwbGF0Zm9ybXMgY2FuJiMzOTt0IGZsb2F0IGluIHRoZSBhaXIsIGJ1dCBuZWVkIHBpbGxhcnMgZm9yIHN1cHBvcnQuIE1vcmUgcHJlY2lzZWx5LCBlYWNoIG9mIHRoZSB0d28gZW5kcyBvZiB0aGUgcGxhdGZvcm0gbmVlZHMgdG8gYmUgc3VwcG9ydGVkIGJ5IGEgcGlsbGFyIHN0YW5kaW5nIG9uIHRoZSBmbG9vciBvciBvbiBhIGRpZmZlcmVudCBwbGF0Zm9ybS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IHdpbGwgYmUgZ2l2ZW4gdGhlIGxvY2F0aW9ucyBvZiB0aGUgcGxhdGZvcm1zIGluIGEgY29vcmRpbmF0ZSBzeXN0ZW0gYXMgaW4gdGhlIGxlZnQgaW1hZ2UgYmVsb3cuIEVhY2ggcGxhdGZvcm0mIzM5O3MgbG9jYXRpb24gaXMgZGV0ZXJtaW5lZCBieSBpdHMgYWx0aXR1ZGUgKHZlcnRpY2FsIGRpc3RhbmNlIGZyb20gdGhlIGdyb3VuZCkgYW5kIHRoZSBzdGFydCBhbmQgZW5kIGNvb3JkaW5hdGVzIGluIHRoZSBob3Jpem9udGFsIGRpcmVjdGlvbi4gRWFjaCBzdXBwb3J0IHBpbGxhciBpcyBwbGFjZWQgaGFsZiBhIHVuaXQgZnJvbSB0aGUgZW5kIG9mIGEgcGxhdGZvcm0sIGFzIGluIHRoZSByaWdodCBpbWFnZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RGV0ZXJtaW5lIHRoZSB0b3RhbCBsZW5ndGggb2YgcGlsbGFycyBuZWVkZWQgdG8gc3VwcG9ydCBhbGwgdGhlIHBsYXRmb3Jtcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wbGF0Zm9ybS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNTBweDsgd2lkdGg6NjI3cHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4sIDEgJmxlOyBOICZsZTsgMTAwLCB0aGUgbnVtYmVyIG9mIHBsYXRmb3Jtcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdGhlIHBvc2l0aW9uIG9mIG9uZSBwbGF0Zm9ybSwgdGhyZWUgY29vcmRpbmF0ZXMgWSwgWDxzdWI+MTxcL3N1Yj4gYW5kIFg8c3ViPjI8XC9zdWI+LiZuYnNwOzxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5UaGUgZmlyc3QgbnVtYmVyIGlzIHRoZSBhbHRpdHVkZSwgdGhlIG90aGVyIHR3byB0aGUgaG9yaXpvbnRhbCBjb29yZGluYXRlcy4gQWxsIGNvb3JkaW5hdGVzIHdpbGwgYmUgcG9zaXRpdmUgaW50ZWdlcnMgbGVzcyB0aGFuIDEwMDAwIHNhdGlzZnlpbmcgWDxzdWI+MjxcL3N1Yj4gJmd0OyBYPHN1Yj4xPFwvc3ViPisxIChpLmUuIHRoZSBsZW5ndGggb2YgZWFjaCBwbGF0Zm9ybSB3aWxsIGJlIGF0IGxlYXN0IDIpLiZuYnNwOzxcL3NwYW4+PFwvcD5cclxuXHJcbjxwPlRoZSBpbnB1dCB3aWxsIGJlIHN1Y2ggdGhhdCBubyB0d28gcGxhdGZvcm1zIG92ZXJsYXAuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSB0b3RhbCBsZW5ndGggb2YgcGlsbGFycyBuZWVkZWQgdG8gc3VwcG9ydCBhbGwgdGhlIHBsYXRmb3Jtcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d