HRT is first and foremost a math and technology company. We are engineers and researchers working as one team to solve difficult problems, and trading millions of shares a day on the world's financial markets.

A new employee at HRT has developed a market-making engine based on the newly designed trading scheme. The developer wishes to analyze the stability of the new engine. The engine uses a virtual account (initially holding no shares) for trading and will follow the strategy below for $N$ contiguous transaction periods (ticks).

• At the $i$-th transaction tick, the engine selects an integer between $a_i$ and $b_i$, inclusive. If the selected integer is positive, it buys an equal number of shares as the integer. If it is negative, the engine sells an equal number of shares as the absolute value of the integer. If it is $0$, the engine does not make a transaction. Shares can be sold even if the engine does not hold a sufficient amount, and in this scenario, the number of shares held becomes negative.
• If the number of shares held right after the $i$-th transaction is $0$, the trading scheme is considered to have minimized position exposure and thus contributed to market stability. In this case, the stability of the engine increases by $x_i$.
• All other factors, such as fees or slippage, are ignored.

Find the maximum stability the new market-making engine can achieve after all $N$ transactions have been completed.

Input

The first line of input contains the number of transactions $N$. ($1 \leq N \leq 1\,000\,000$)

The $i$-th of the following $N$ lines contains three space-separated integers $a_i, b_i, x_i$, denoting the information about the $i$-th transaction. ($-10^9 \leq a_i \leq b_i \leq 10^9$; $1 \leq x_i \leq 10^9$)

Output

Print the maximum stability the new market-making engine can achieve after all $N$ transactions have been completed.

Examples

Input 1

3
-1 0 3
1 1 2
-1 0 5

Output 1

8

Input 2

5
1 1 1000
-2 -1 7
1 1 5
-1 -1 4
1 1 8

Output 2

13

Input 3

8
-1 1 5
-4 2 7
3 4 4
-6 4 8
-2 -1 6
-5 7 1
4 6 9
-7 7 5

Output 3

34