405007: GYM101736 G Game

Our little Cactus friend is back with an interesting game! This game features a wheel which consists of n compartments connected in a loop. Each compartment has a hole leading out of the loop. To play, the ball is randomly put into one of the compartments, and the player simply watches it roll around the loop. After some time, the ball will exit through one of the holes, and the game ends. Once the ball exists the wheel, the player is given a score based on the hole from which it exited, and the compartments that the it had visited (counting multiplicity).

More precisely, if the ball is at compartment i for 1 ≤ i < n, it may exit the wheel with probability p_i or it may move on to compartment i + 1 with probability 1 - p_i. If the ball is at compartment n, it may exit the wheel with probability p_n or move on to compartment 1 with probability 1 - p_n. The player begins with a score of 0. Each time the ball visits compartment i, the player gains a_i score. If the last compartment the ball was in before it exited the loop was compartment j, the player gains an additional b_j score.

All that is left is for Cactus to assign probabilities. To make things interesting, he wants to assign probabilities so that 0.01 ≤ p_i ≤ 0.99. Since the score counting contraption cannot handle very large numbers, Cactus wants to minimize the expected score. Your task is to calculate the minimum possible expected score while the probabilities satisfy the given restriction. You may assume that the initial compartment is chosen uniformly at random.

The first line of input contains a single integer n (2 ≤ n ≤ 500), the number of compartments in the wheel.

Each of the next n lines contains two space-separated integers a_i and b_i, (1 ≤ a_i, b_i ≤ 10⁶), describing the ith compartment. a_i is the score gained each time the ith compartment is visited, and b_i is the score gained if the ith compartment is the last compartment visited.

Print, on a single line, the minimum possible expected score. Your answer will be considered correct if it is within 10^- 6 absolute or relative error.

3
1 100
1 100
1 1

4.0227937347

2
420 3
1 1

214.6262626263