LUNAPARK

A theme park is planning to install new recreational activities. The engineers have identified a set of possible locations along an imaginary straight line. Each location is suitable for a specific activity, the installation of which yields a specific profit. For each activity installed, space must be provided for public entry and exit. To make the best use of space, the entry and exit areas of neighboring activities can overlap, while entry and exit spaces have been secured for the first and last activity, respectively. However, the installation of one activity may exclude the installation of other activities in neighboring positions before and after it.

For example, consider a small park with ~4~ candidate positions. In the first position, a roller coaster can be installed with a daily profit of ~225~ euros. The roller coaster requires ~3~ empty positions to the right as an exit area. In the second position, bumper cars can be installed with a daily profit of ~150~ euros. The bumper cars require one empty position to the left and one empty position to the right. In the third position, the "octopus" ride can be installed with a daily profit of ~210~ euros. The "octopus" requires one empty position to the left and one empty position to the right. In the fourth position, a trampoline can be installed with a daily profit of ~90~ euros. The trampoline requires one empty position to the left. The optimal solution is to install the bumper cars in the second position and the trampoline in the last position, yielding a daily profit of ~240~ euros.

The park's engineers need our help in selecting the activities to be installed in order to maximize the park's profit. Write a program that solves the engineers' problem.

Input

The program should read from the standard input a positive integer ~N~, corresponding to the number of activities in the park. From the next ~N~ lines, the program will read ~3~ integers corresponding (in the order given) to the profit ~C_i~ generated by installing activity ~i~, and the number of empty positions to the left ~L_i~ and to the right ~R_i~ required for installing activity ~i, i = 1, ..., N~. The activities are numbered based on their position along the line, from left to right.

Output

An integer corresponding to the maximum profit for the business.

Constraints

• ~1 \le N \le 100.000~
• ~0 \le C_i \le 2000~
• ~0 \le L_i,R_i \le 100~

Bonus There will be an extra input example for which:

~0 \le L_i, R_i \le 100.000~

• Time Limit: 1 sec.
• Maximum available memory: 64 MB.

Example of Input - Output

STDIN (lunapark.in)

5
80 0 1
60 1 1
90 1 2
100 2 1
70 1 0

STDOUT (lunapark.out)

180