407756: GYM102890 G Gold Fever

A gold rush or gold fever is a new discovery of gold that brings an onrush of miners seeking for fortune. Major gold rushes took place in the 19th century in Australia, New Zealand, Brazil, Canada, South Africa and the United States, while smaller gold rushes took place elsewhere.

In the 19th century the wealth that resulted was distributed widely because of reduced migration costs and low barriers to entry. While gold mining itself proved unprofitable for most diggers and mine-owners, some people made large fortunes while merchants and transportation facilities made large profits. The resulting increase in the world's gold supply stimulated global trade and investment. Historians have written extensively about the mass migration, trade, colonization and environmental history associated with gold rushes.

A rush typically begins with the discovery of placer gold made by an individual. At first the gold may be washed from the sand and gravel by individual miners with little training, using a gold pan or similar simple instrument. Winning the gold in this manner requires almost no capital investment, only a simple pan or equipment that may be built on the spot, and only simple organisation.

Bob has found an interesting book explaining some weird methods used by miners to maximize the gold they obtained from a river during the 19th century gold fever, the book explains some miners would divide the river in $$$N$$$ sections numbered from $$$1$$$ to $$$N$$$, and start panning for gold on any of the river sections, after panning the gold $$$g_i$$$ in a given section $$$i$$$ of the river, the miner will continue panning the gold in another section with a number between $$$i + a_i$$$ and $$$i + b_i$$$. Miners using this method would never walk backwards to not be suspicious of them looking for more gold, the fewer looking for gold in a river the more gold a miner would be able to win. Some time later, Bob found in the same book records of the rivers explored by some miners, each of these records have the amount of gold the river had on each section and the values $$$[a_i ,b_i]$$$ that would be used to determine the next section to go on after getting the gold in each section.

As bob knows your programming skills, he wants some help to find what would be the maximum amount of gold a single miner would be able to get following the method described in his book, if he knew beforehand all the information in the records Bob found.

The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), representing the number of sections the river is divided into. Each of the following $$$N$$$ lines contain three integers separated by a space, $$$g_i$$$, $$$a_i$$$, $$$b_i$$$ ($$$0 \leq g_i \leq 100$$$, $$$1 \leq a_i \leq b_i \leq N$$$), representing respectively, the amount of gold in section $$$i$$$, and the range $$$[a_i, b_i]$$$ used by the miners to determine the next section to go for gold.

Output a line containing one integer. The maximum amount of gold a single miner would be able to get following the method described in Bob's book.

5
1 1 1
1 1 1
3 1 2
5 2 3
10 1 1

15

8
7 3 5
2 3 5
1 3 5
3 3 5
9 3 5
2 3 5
1 3 5
3 3 5

19