Millionaire

Congratulations, you have been picked for the TV quiz show Who Wants to Be a Millionaire. Like most people you are somewhat risk averse, so you might rather take $250,000 than a 50% chance at $1,000,000. If you happen to be rich already, the gamble looks better. Before the show you want a strategy that maximizes the expected happiness your winnings bring.

More precisely, if your present net worth is $W$ dollars, then winning $v$ dollars gives you $\ln(1 + v/W)$ units of happiness. The expected happiness of the game is $\sum_v P(v) \ln(1 + v/W)$, where $P(v)$ is the probability that you win $v$ dollars and the sum runs over every possible value of $v$. Happiness units are too abstract to report, so measure the value of the game in dollars: compute $D$, the guaranteed payout that makes you exactly as happy as playing the show with optimal strategy.

The show asks $n$ trivia questions in a fixed order. Question $i$ carries a prize of $v_i$ dollars, and your analysis of past episodes says your chance of answering it correctly is $p_i$.

After a correct answer you choose to quit or to continue. If you quit right after answering question $i$ correctly, you win $v_i$ dollars, and if you continue you must attempt question $i+1$. If you answer every question correctly, you win the prize of the last question, $v_n$ dollars.

If you answer a question incorrectly, the game ends at once and you win the prize of the last question you answered correctly among those marked safe. If you never answered a safe question correctly, you win nothing.

For example, take $W = 4000$ with a single unsafe question whose prize is $5,000 and whose success probability is $0.5$. The game is worth $0.5 \ln(1 + 5000/4000) \approx 0.405$ units of happiness, and a guaranteed $2,000 grants $\ln(1 + 2000/4000) \approx 0.405$ as well, so $D = 2000$.

The first line contains two space-separated integers $n$ and $W$ ($1 \le n \le 10^5$, $1 \le W \le 10^6$). Line $i+1$ describes question $i$. It starts with the string safe or unsafe, telling whether question $i$ is safe, followed by a real number $p_i$ and an integer $v_i$ ($0 \le p_i \le 1$, $1 \le v_i < v_{i+1} \le 10^6$).

Print one line holding a $ sign immediately followed by $D$, rounded to exactly two decimal places.