ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

## Ural FU Open Personal Contest 2014

Contest is over

Time limit: 2.0 second
Memory limit: 64 MB
Winter in Yekaterinburg is the longest time of the year. And everyone spends long winter evenings in his own way. For Fedor this evening is very special, because for the first time in many years the legendary German rock band Decline gives a concert in Yekaterinburg. Fedor needs to go through the city to the concert hall. And, as ill luck would have it, this day the snow began to fall, thoroughly slowing down the traffic on all roads. A snow-clearing equipment slightly saves the situation, but during the cleaning of the road the driving through it is closed.
In normal weather Fedor can drive through the i-th road in time ti. In the snowfall, travel time depends on the amount of snow on a road. If Fedor starts his travel through the i-th road after time T after its last cleaning (or after the beginning of a snowfall, if this road has not been cleaned yet), the travel time through it will be equal to min(⌈(1 + T/100) · ti⌉, 100500 · ti) (⌈x⌉ is x rounded upwards).
Fedor has found on the Internet a complete plan of roads cleaning. He wants to construct his route without driving through a road during its cleaning (and always leaving a road before its next cleaning). Fedor may be waiting on the crossroads for the moment when he can drive further. He needs to select a route which allows him to get to the concert hall as soon as possible.

### Input

The next line contains an integer k (1 ≤ k ≤ 105). The following k lines contain the plan of roads cleaning. The i-th one contains integers pi, si and fi that are the road number and moments when the cleaning will be started and finished (1 ≤ pim; 0 ≤ si < fi ≤ 109). During the evening the same road can be cleaned several times, but one of its cleaning always ends up strictly before the next one begins.
Fedor leaves his house at the beginning of a snowfall. All times are counted from that moment and measured in minutes.

### Output

Output the minimum time in which Fedor will be able to get to the concert hall.

inputoutput
```4 3
1 2 10
2 3 10
3 4 10
1
2 10 15
```
```38
```

### Notes

In the example, Fedor passes the first road in 10 minutes, then waits 5 minutes at the second crossroad for the end of the cleaning, then passes the second road in 10 minutes. 25 minutes after the start, he goes to the third road and passes it in 13 minutes (because of the snow that had fallen on it during 25 minutes of snowfall).
Problem Author: Denis Dublennykh
Problem Source: Open Ural FU Personal Contest 2014
To submit the solution for this problem go to the Problem set: 2093. All Roads Lead to Snowdrift