SLUMDOG MILLIONAIRE

Most of us would be familier with the film named Slumdog Millionaire, which was nominated for ten Academy Awards in 2009 and won eight, the most for any film of 2008, including Best Picture and Best Director. It also won five Critics' Choice Awards, four Golden Globes, and seven BAFTA Awards, including Best Film.
Jamal Malik, the protagonist in the story, is an 18 year-old orphan from the slums of Mumbai, who is participating an India's "Who Wants To Be A Millionaire?" program. With the whole nation's watching, he successfully figured out the key to the seemingly impossible questions and finally, albeit once he was accused of cheating before the last quesion, winning the staggering 20 million rupees.
The reason why Jamal Malik could pass the series of tough quizzes is simplely based on his life experiences and a lucky guess. But now, if your are on that game show program, would you be an another lucky dog ?
The rule of the game show is quite simple: you would be offered N questions, each of them worth Vi ruppes. Within each round, you are free to choose quit and keep the prize you had won so far or continuing answer the question in order to gain more wealth.If you succesfully answer the i-th question, the aggregate of your winning prize would accumulate by Vi and you get the chance of advancing to the next round, otherwise, you quit the game with nothing. During each round, you are able to assess the probability p that you could answer it, which can help you make the right decision whether answer it or not. Note that you are also offered M kinds of Life Lines, each of them could be used only once. We assume that, to make the problem easier, after using a Life Line, definitely, you could succesfully survive in that round, regardless of the difficulity of that problem.

The first line is an integer T ( T <= 100) , representing the number of test cases, followed by T test cases, each test case begins with two integers N (0< N <= 200) and M ( 0<= M <= 10), representing the number of questions and Life Lines respectively and then followed by N lines, the i-th line represents the i-th question, containing 2 elements: Vi (the award of the i-th question) and Pi (the probability you could answer it). Note that Vi is an positive integer no greater than 100, 000 and Pi is a float number belongs to the interval [0,1].

The output for each test case begins with a line containing "Case i:", where i is the number of the case starting at 1. In the next line, print the player's expect prize, if he plays the best strategy. Output should be rounded to three fractonal digits.

3
1 0
300 0.5
1 1
300 0.5
2 1
300 0.1
500 0.9

Case 1:
150.000
Case 2:
300.000
Case 3:
720.000

HDU 8th Programming Contest Site（2）