Description

For a certain game, we plan to build some platforms, and the positions of all platforms have already been chosen. Based on common sense, platforms cannot float in the air without support. More precisely, both ends of any platform must either have a pillar or rest on another platform.

You are given the coordinates of each platform in a coordinate system (as in the figure). Each platform is specified by its height (the vertical distance from the floor) and its horizontal span (start and end). Each pillar is placed half a unit away from the edge of the platform it supports (see figure).

Compute the total length of pillars needed to support all platforms.

Input Format

The first line contains $1$ integer $N$, the total number of platforms.

Each of the next $N$ lines contains the coordinates of a platform: the corresponding $Y$, $X_1$, and $X_2$, i.e., its height and the horizontal coordinates of its endpoints.

Output Format

Output the total length of pillars required to support all platforms.

3
1 5 10
3 1 5
5 3 7

14

Hint

Constraints

For all test points, it is guaranteed that $1 \le N \le 100$, all coordinates are positive integers not greater than $10000$, and they satisfy $X_2 > X_1 + 1$ (equivalently, each platform has length at least $2$). For any two platforms at the same height, there is no overlap between them.

Notes

Translated from COCI2007-2008 Regional Competition T1 PLATFORME.

Translated by ChatGPT 5