Guard and Crystal Lamps

A row of crystal lamps is set on every integer point on the positive half‐axis. Initially all lamps are lit. At time \(0\) a guard stands at the origin. Every unit of time the guard can move one unit left, one unit right, or simply stay still. In addition, whenever the guard is at a point with a crystal lamp she may turn off the lamp immediately (this action does not consume extra time).

There are \(n\) requests. Each request is given as a triple \((l_i, r_i, t_i)\) which means that every lamp at an integer point in the interval \([l_i,r_i]\) must be extinguished, but none of these lamps may be turned off before time \(t_i\) (i.e. before time \(t_i\) the guard is not allowed to turn off any lamp in \([l_i,r_i]\) ).

The guard may choose the order in which to turn off the lamps. Note that if a lamp is required by several requests then it must be turned off at a time that is not earlier than the largest of the corresponding \(t_i\) values. In other words, for every request \((l_i,r_i,t_i)\) and for every integer \(x\) with \(l_i\le x\le r_i\), if lamp \(x\) is turned off at time \(T_x\) then it must hold that \(T_x\ge t_i\).

Your task is to compute the minimum number of time units the guard needs in order to finish turning off all lamps required by all villagers’ requests.

Observation: It is always necessary to eventually turn off the lamp positioned at the far right of all required intervals. In an optimal strategy the guard can postpone turning a lamp off until she is at its leftmost point. Hence a simple lower bound (which is in fact achievable) is given by \[ \text{answer} = r_{\max} + \max\Big(0, \max_{1\le i\le n}(t_i-l_i)\Big), \] where \(r_{\max}\) is the maximum \(r_i\) among all requests. You are to implement a program that, given \(n\) and the \(n\) triples \((l_i,r_i,t_i)\), computes this minimum time.

Note: It can be proved that the strategy achieving the time above (i.e. go directly from 0 to the leftmost required lamp of the request having the maximum value of \(t_i-l_i\), wait if necessary, and then proceed to \(r_{\max}\)) indeed satisfies all requests.

inputFormat

The first line contains a single integer \(n\) (\(1\le n\le 10^5\)), the number of requests. Each of the next \(n\) lines contains three integers \(l_i, r_i, t_i\) (\(1\le l_i\le r_i\le 10^9\), \(0\le t_i \le 10^9\)).

It is guaranteed that the lamps are placed on every positive integer point, but only the lamps in some intervals are required to be turned off.

outputFormat

Output a single integer, the minimum number of time units needed for the guard to complete all requests.

sample

2
1 1 100
10 10 0

109