Optimal Chessboard Game Strategy

Alice and Bob play a strategic board game on a 1×(n+1) board, with cells numbered 0, 1, 2, …, n (cell n is the terminal). For each cell i (0 ≤ i ≤ n-1) there are two associated positive integers, p_i and q_i. A piece starts at cell 0. Players take turns (Alice moves first) and from a cell k the current player must move the piece forward by an integer number of cells x (1 ≤ x ≤ p_k) so that the new cell is k+x. If the player moves less than the maximum allowed (i.e. if x < p_k) and k+x is not the terminal cell, the player may choose to initiate a challenge.

When a challenge is issued at cell k with a chosen step x (x < p_k), two independent random integers are generated:

• u is uniformly chosen from {1, 2, …, p_k - x}.
• v is uniformly chosen from {0, 1, …, q_k + q_k+x}.

The challenge outcome is determined as follows:

• If u > v: the challenge succeeds. The opponent loses one turn, and the same player continues with an extra move. Note: on such extra moves the player cannot initiate a challenge.
• If u = v: the challenge is a tie and nothing special happens. The turn passes normally to the opponent.
• If u < v: the challenge fails. The current player’s next move is skipped, giving the opponent an extra move. However, when a player receives an extra move in this manner, they are not allowed to issue a challenge on that move; they may only consider a challenge after that first extra move.

In any move a player must move at least 1 cell. The game ends when someone moves the piece onto cell n – that player wins. Both players are assumed to play optimally to maximize their own winning probability. Your task is to compute the probability that Alice wins when starting from cell 0 with the first move and full challenge possibilities.

Game dynamics summary:

• From cell k (0 ≤ k ≤ n-1) with values p_k and q_k, a move is to choose an integer x (1 ≤ x ≤ min(p_k, n-k)).
• If x = p_k (i.e. full movement), no challenge is allowed and the turn passes to the opponent.
• If x < p_k, the player may optionally initiate a challenge. The computed challenge probabilities use:
  Let L = p_k - x and M = q_k + q_k+x + 1. Then:
  • Count of success outcomes = L(L+1)/2
  • Count of tie outcomes = min(L, (M-1))
  • Count of failure outcomes = L×M - L(L+1)/2 - min(L, (M-1))
• After a normal move without challenge the turn passes to the opponent, and the winning probability is 1 - (opponent’s winning probability) from the new cell. In extra moves (from a successful challenge or due to opponent’s challenge failure) the player’s ability to challenge may be locked for the first move.

Your program should determine, using optimal play from both sides, the probability that Alice wins.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ N), where the board has n+1 cells (0 to n). Then follow n lines. The i-th of these lines (0 ≤ i ≤ n-1) contains two integers: p_i and q_i (1 ≤ p_i ≤ some limit, 0 ≤ q_i ≤ some limit), representing the parameters associated with cell i.

You may assume that moves always keep the piece within the board.

outputFormat

Output a single real number – the probability that Alice wins the game when playing first from cell 0. The answer will be accepted if it has an absolute or relative error of at most 1e-6.

sample

1
1 0

1.000000