URI Online Judge | 2905

Cheap Trips

Por Alejandro Strejilevich de Loma BR Brazil

Timelimit: 1

Nlogonia has a new scheme for public transportation. When the first trip of a passenger starts, it also starts a 120 minutes interval such that discounts are applied to some of the trips that the passenger starts before the end of the interval. The discount for the second trip is 50% of the regular cost, while the discount for each of the remaining trips up to the sixth trip (that is, four more trips) is 75% of the regular cost. Once the 120 minutes interval ends, a new trip starts a new interval having the same kind of discounts.

Astor is an exchange student that has just arrived to Nlogonia. He wants to spend as little money  as possible for making a sequence of trips. The first trip in the sequence can be started at any time. Each trip but the first one cannot be started before the previous trip in the sequence ends, although it can be delayed as much as needed. Given the duration and the regular cost of each trip in the sequence, can you tell Astor the minimum cost he must afford so as to complete all the trips in the sequence?


The first line contains an integer N (1 ≤ N ≤ 104 ) representing the number of trips in the sequence. Each of the next N lines describes a trip with two integers D and C (1 ≤ D, C ≤ 1000), indicating respectively the duration (in minutes) and the regular cost of the trip.


Output a single line with a number representing the minimum cost needed to complete all the trips in the order they appear in the input. The result must be output as a rational number with exactly two digits after the decimal point, rounded if necessary.

Exemplos de Entrada Exemplos de Saída


120 10

10 30



110 10

10 30

1000 101



10 1

10 2

10 4

10 4

10 4

10 4

10 1