Branimirko is still a passionate player of the world-renowned game Pokémon Go. Recently, he decided to organize a competition in catching Pokémon. It will be held in Ilica street in Zagreb, and the main sponsor is his friend Slavko. The reward is, of course, candy!
Ilica is, as we all know, the longest street in Zagreb. There are
Before the competition, Branimirko looked at the map and saw
Branimirko can visit one house number per second. Also, when he catches a Pokémon, that Pokémon disappears from the map.
Since Branimirko really likes candy, he asked for your help. Help him and determine the maximal amount of candy he can get!
Input Specification
The first line of input contains integers
Each of the following
In the input data, the Pokémon will always be in a strictly ascending order by house number
Output Specification
You must output the required maximal amount of candy from the task.
Scoring
In test cases worth
In additional
Sample Input 1
10 5 4
1 30 4
3 5 7
7 10 12
9 100 23
Sample Output 1
115
Explanation for Sample Output 1
One strategy is that Branimirko first catches the Pokémon at house number 3 (5 candy), then, respectively, house numbers 7 (10 candy) and 9 (100 candy) for a total of 115 candy. Notice that Branimirko can't catch the Pokémon at house number 1, because he can't reach it in time from his starting position (house number 5).
Sample Input 2
20 8 7
1 35 14
4 57 1
6 32 2
9 94 28
14 78 8
15 8 1
17 55 3
Sample Output 2
172
Comments