시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB888100.000%

## 문제

Congratulations! You were selected to take part in the TV game 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 of winning \$1,000,000. On the other hand, if you happen to already be rich, then you might as well take a chance on the latter. Before appearing on the show, you want to devise a strategy to maximize the expected happiness derived from your winnings.

More precisely, if your present net worth is W dollars, then winning v dollars gives you ln(1 + v/W) units of happiness. Thus, the game’s expected happiness is ΣvP(v) ln(1+v/W), where P(v) is the probability that you’ll win v dollars, and the summation is taken over all possible values of v. Since happiness units are too abstract, you will be asked to measure the value of the game in dollars. That is, compute D such that a guaranteed payout of D dollars makes you as happy as a chance on the show, assuming optimal play.

On the show, you will be presented with a series of questions on trivia, each associated with a prize value of vi dollars. Your analysis of past episodes reveals that if you attempt the ith question, your chances of being correct are pi.

After answering correctly, you may choose to continue or to quit. If you quit, you win the value of the last correctly answered question; otherwise, the game continues and you must attempt the next question. If you correctly answer all the questions, you walk away with the value of the last question.

If you answer a question incorrectly, however, the game ends immediately and you win the value of the last correctly answered question that is labeled as safe, or nothing if you never solved a safe question.

## 예제 입력 1

1 4000
unsafe 0.5 5000




## 예제 입력 3

2 4000
safe 0.003 1
safe 0.03 10


## 예제 출력 3

\$0.00