Problem H
Roller Coasters are Fun Fun Fun (But Waiting is Not)

You’ve just arrived at your favorite amusement park (Fun Fun Fun Land), and can’t wait to ride the (fun) roller coasters. Like every other patron, you are trying to maximize the amount of fun you have. We will represent the amount of fun you are having by ‘fun points’. When you arrive at the amusement park you have $100$ fun points. You lose fun points by walking between rides and while waiting for rides, but gain major fun points when you ride! However, great fun is always impeded by restrictions$\ldots $

You are accompanied by your (picky) best friend who is visiting from NotSoFun Town, and has a four requirements

1. you must ride every roller coaster exactly once,

2. you must leave Fun Fun Fun Land the same way you entered,

3. your fun points may never be negative, and

4. you must leave Fun Fun Fun Land with the maximum number of fun points possible.

There are $N$ roller coasters $r_1, r_2, \ldots , r_ N$, with waiting times $w_1, w_2, \ldots , w_ N$ in minutes and fun-point gains of $f_1, f_2,\ldots , f_ N$, respectively. Furthermore, for simplicity, the entrance/exit and all roller coasters are evenly spaced on a $1$D line. Roller coaster $r_1$ is $1$ minute’s walk from the entrance/exit, and each roller coaster $r_ i$ is $1$ minute’s walk from its predecessor $r_{i-1}$.

After each minute you wait at a ride, $5$% of your current fun points are deducted. If this value is non-integral, round down the deducted points. For every minute spent walking, $8$ fun points are deducted. Consider the following simple amusement park:

One possible visit is to ride $r_1$ and then $r_2$. To do this you walk from the entrance to $r_1$ ($-8$ fun points), wait for $r_1$ ($-\lfloor 0.05\cdot 92\rfloor = -4$ for the first minute and $-\lfloor 0.05\cdot 88\rfloor = -4$ for the second minute), ride $r_1$ ($+10$), walk to ride $r_2$ ($-8$), wait for $r_2$ (-$\lfloor 0.05\cdot 86\rfloor = -4$), ride $r_2$ ($+50$) and then walk to the exit ($-16$), yielding

fun points in total.

Following similar logic, riding $r_2$ and then $r_1$ yields fewer fun points, at

fun points. Therefore, the maximum number of fun points you can yield on your visit is $116$.

Note that if your points become negative at any time during a visit (for example, if you leave a ride with $7$ points and walk 1 minute), such a visit is invalid and as your friend’s criteria are not met. Every amusement park given will have a valid visit.

How many fun points can you yield during your visit to Fun Fun Fun Land?

Input

The input consists of $N$ roller coaster rides. The first line is the integer $N$, which has the restriction $1 \leq N \leq 50$. This is followed by $N$ lines, each containing a space-separated pair of integers: the $i$-th of these lines contains the waiting time $w_ i$ and fun-point gain $f_ i$ for roller coaster $r_ i$. Where $1\leq w_ i, f_ i \leq 128$.

Output

The maximum number of fun points that you can yield after visiting the amusement part. Your answer should be an integer outputted on a single line.

2
2 10
1 50

116

3
1 2
1 3
1 5

53

3
1 2
4 20
2 19 

71

4
114 42
127 49
123 81
124 6

76