A Beautiful Game: Maximizing Expected Damage

Little K, having been brainwashed by the LL cult, is determined to have one final beautiful game of Arthur. As you know, Arthur is a game of chance. Each card in the fixed sequence has a skill with a probability of success and a damage value. When playing a game, there are \(n\) cards arranged in a fixed order (from 1 to \(n\)). The game is played in \(r\) rounds. In each round, the system processes the cards in order from the first to the last with the following rules:

1. If the card has already activated its skill in a previous round:
   1. If it is not the last card, simply skip it and move on to the next card;
   2. If it is the last card, immediately end the current round.
2. If the card has not yet activated in the current game, let this be the \(i\)th card:
   1. Attempt to activate its skill with probability \(p_i\) (with \(0<p_i<1\)).
   2. If the skill activates, deal \(d_i\) damage to the enemy and immediately end the round.
   3. If the skill does not activate and the card is the last card (i.e. \(i=n\)), then end the current round; otherwise, proceed to the next card.

Once a card activates its skill in any round, it will not be attempted in future rounds. Note that if a card fails to activate, it remains available in later rounds. Help Little K by computing the expected total damage dealt in a game.

The process can be modeled recursively. Let \(F(i,R)\) denote the expected damage from cards \(i, i+1, \ldots, n\) with \(R\) rounds remaining. For \(1 \le i \le n-1\), we have:

[ F(i,R) = d_i\Bigl[1-(1-p_i)^R\Bigr] + \sum_{j=1}^{R} (1-p_i)^{j-1}p_i, F(i+1,R-j),\quad \text{for }R\ge1, ]

and for the last card (i.e. \(i=n\)):

[ F(n,R) = d_n\Bigl[1-(1-p_n)^R\Bigr]. ]

Output \(F(1,r)\), the expected damage for the entire game.

inputFormat

The first line contains two integers \(n\) and \(r\) (the number of cards and rounds, respectively). Each of the following \(n\) lines contains two numbers: \(p_i\) and \(d_i\), representing the success probability and the damage of the \(i\)th card. Note that \(0 < p_i < 1\).

outputFormat

Output a single floating-point number representing the expected total damage caused in the game. Your answer will be accepted if it has an absolute or relative error of at most \(10^{-6}\).

sample

1 5
0.5 10

9.6875