Chain Reaction Minesweeper

In a linear minefield, several mines are placed along a straight line. Each mine is characterized by a coordinate x and an explosion power p. When a mine detonates (either via manual triggering or by a chain reaction), it will immediately detonate its adjacent neighbors if they lie within its explosion range. Formally, when mine i (with coordinate \(x_i\) and explosion power \(p_i\)) explodes:

• If \(i \gt 1\) and \(x_i - x_{i-1} \le p_i\), then mine i-1 will also explode.
• If \(i \lt n\) and \(x_{i+1} - x_i \le p_i\), then mine i+1 will also explode.

This chain reaction continues recursively: any mine detonated by the chain reaction will, in turn, trigger its adjacent neighbors provided the same condition holds. Note that the chain reaction is directional; a mine can only trigger a neighbor if the gap between them is no more than the exploding mine's explosion power.

For convenience, we define for each mine the left and right spread (when that mine is detonated manually) as follows. Assume the mines are sorted by coordinate (i.e. \(x_1 < x_2 < \cdots < x_n\)). For a mine at index \(i\) (using 1-indexing):

• Left spread: Let \(L[i]\) be the smallest index reached by a chain reaction when mine \(i\) is detonated. This is computed by starting at \(i\) and while \(i > 1\) if \[ x_i - x_{i-1} \le p_i, \] set \(i = i-1\). In other words, \[ L[i] = \min\{j : \forall k \; (j+1 \le k \le i), \; x_k - x_{k-1} \le p_k\}. \]
• Right spread: Similarly, let \(R[i]\) be the largest index reached when mine \(i\) is detonated. That is, starting at \(i\) and while \(i < n\) if \[ x_{i+1} - x_i \le p_i, \] then \(i\) is extended to \(i+1\). Formally, \[ R[i] = \max\{j : \forall k \; (i \le k \le j-1), \; x_{k+1} - x_k \le p_{k+1}\}. \]

The robot clears the minefield by repeatedly performing a manual detonation according to the following randomized process:

1. While there are still unexploded mines, choose one uniformly at random from those remaining.
2. Detonate that mine manually. This triggers a chain reaction that automatically explodes all mines in a contiguous block \([L_i, R_i]\) (where the effective boundaries within the current interval are taken into account).

Your task is to compute the expected number of manual detonations needed to clear all mines.

Note: Since the chain reaction from a manually detonated mine clears a contiguous segment, if we consider an interval \([l, r]\) (with indices in the sorted order), and if a mine at index \(i\) is chosen, the explosion will clear all indices from \(\max(L[i], l)\) to \(\min(R[i], r)\). Then the process continues recursively on the remaining segments.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 200\)), representing the number of mines. The following \(n\) lines each contain two integers: \(x_i\) and \(p_i\) (\(1 \le x_i, p_i \le 10^9\)). It is guaranteed that \(x_1 < x_2 < \cdots < x_n\).

outputFormat

Output the expected number of manual detonations needed. Your answer will be accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

3
1 1
3 2
6 1

2.500000