Bakejoon Online Judge is an online judge where users bake and submit bread that satisfies unusual conditions.
As a user of Bakejoon Online Judge, you must submit $N$ fresh loaves of bread all at once satisfying the following conditions.
At most one loaf of bread can be baked at a time, and once you start baking a loaf, you cannot stop it midway.
Each loaf of bread has three characteristics: preparation time $P_i$, baking time $T_i$, and freshness duration $F_i$.
- Since preparation is needed before baking, the $i$-th loaf can be baked starting from time $P_i$.
- It takes $T_i$ units of time to bake the $i$-th loaf.
- The $i$-th loaf remains fresh for $F_i$ units of time from the moment it is fully baked.
More precisely, if you start baking the $i$-th loaf at time $t \ge P_i$, then it becomes fully baked at time $t+T_i$, and it remains fresh from time $t+T_i$ to time $t+T_i+F_i$. The loaf is also fresh at the times $t+T_i$ and $t+T_i+F_i$.
Given the characteristics of the $N$ loaves of bread, determine whether it is possible to submit all loaves while they are fresh, and if it is possible, find the earliest time at which they can be submitted.
Input
The first line contains the number of loaves of bread $N$.
$$1 \le N \le 200\,000$$
Each of the next $N$ lines contains three integers $P_i$, $T_i$, and $F_i$, separated by spaces: the preparation time, baking time, and freshness duration of each loaf of bread.
$$0 \le P_i,T_i,F_i \le 10^9$$
Output
Print the earliest time at which all $N$ loaves of bread can be submitted while they are fresh. If it is impossible to submit all $N$ loaves while they are fresh, print -1 instead.
Examples
Example 1
Input
4
2 0 4
4 1 2
1 2 0
0 3 7Output
7Example 2
Input
3
0 1 1
1 1 1
2 1 1Output
-1Note
In the first example, if the loaves are baked in the following way, all loaves can be submitted while they are fresh at time $7$.
| Loaf | Baking time interval | Fresh time interval |
|---|---|---|
| 1 | instantaneously at time $5$ | $[5,9]$ |
| 2 | $[4,5]$ | $[5,7]$ |
| 3 | $[5,7]$ | only at time $7$ |
| 4 | $[0,3]$ | $[3,10]$ |
Thus, loaf 4 is baked from time $0$ to time $3$, loaf 2 from time $4$ to time $5$, loaf 1 instantaneously at time $5$, and loaf 3 from time $5$ to time $7$; all four loaves are fresh at time $7$.
In the original figure, a gray X means that the loaf is not ready to be baked yet, a green P means that the preparation is complete, a red T means that the loaf is being baked in the oven, a blue F means that the loaf is fresh, and a yellow R means that the loaf is no longer fresh.
In the second example, no matter how the loaves are baked, it is impossible to make all $3$ loaves fresh at the same time.