Little Petya likes travelling a lot. There are N cities in his country, Berland. These cities are situated on
a single line. Petya numbered them from 1 to N in the increasing order of their beauty. Petya lives in the
city 1 and he wants to get to the city N . He doesn’t want to spoil the impression about the trip, so he
decided to visit cities in the increasing order of their numbers (remember, that he numbered them in the
increasing order of their beauty).
To move between the cities, Petya chose the only aircompany in his country “Berland Airlines”. The cost of flight from city i to city j equals ci·|xi −xj|+tj , where xi is the coordinate of city i, xj is the coordinate
of city j, ci is the cost of unit of fuel in the city i and tj is the tax for entering the city j. Petya expects this trip to be the best trip in his life, so he decided to spend as much money as possible for it. Help him to determine the maximum amount of money he can spend. Note that it is not necessary to visit all cities.
There are multiple test cases.
First line of each test case contains one integer N (1 ⩽ N ⩽ 100 000) — the number of cities in Berland. i-th of the next N lines contains three integers: xi (−106 ⩽ xi ⩽ 106 ), ci (1 ⩽ ci ⩽ 106 ) and ti (1 ⩽ ti ⩽ 106 ).
All coordinates of cities are distinct.
Output the maximum amount of money Petya can spend. It is guaranteed that for all given test cases, the answer will not exceed 1012.
4 5 10 2 0 1 10 15 3 14 17 2 3
123
Here are two possible optimal routes: 1 → 4, 1 → 3 → 4.
Migrated from old NTUJ.
2010 summer petrozavodsk training camp
| No. | Testdata Range | Score |
|---|