2014
01-05

# 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 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].

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

1. 100多分钟的煞笔电影，坚持在电影院看完后我问收回3D眼镜的“可以退票吗？”那人说“我说了不算啊”，这电影简直模仿抗日神剧啊，一弓箭射掉2架战斗机，其余的剧情一直在哔哔！

2. 100多分钟的煞笔电影，坚持在电影院看完后我问收回3D眼镜的“可以退票吗？”那人说“我说了不算啊”，这电影简直模仿抗日神剧啊，一弓箭射掉2架战斗机，其余的剧情一直在哔哔！

3. 100多分钟的煞笔电影，坚持在电影院看完后我问收回3D眼镜的“可以退票吗？”那人说“我说了不算啊”，这电影简直模仿抗日神剧啊，一弓箭射掉2架战斗机，其余的剧情一直在哔哔！

4. 100多分钟的煞笔电影，坚持在电影院看完后我问收回3D眼镜的“可以退票吗？”那人说“我说了不算啊”，这电影简直模仿抗日神剧啊，一弓箭射掉2架战斗机，其余的剧情一直在哔哔！

5. 100多分钟的煞笔电影，坚持在电影院看完后我问收回3D眼镜的“可以退票吗？”那人说“我说了不算啊”，这电影简直模仿抗日神剧啊，一弓箭射掉2架战斗机，其余的剧情一直在哔哔！

6. 100多分钟的煞笔电影，坚持在电影院看完后我问收回3D眼镜的“可以退票吗？”那人说“我说了不算啊”，这电影简直模仿抗日神剧啊，一弓箭射掉2架战斗机，其余的剧情一直在哔哔！

7. 100多分钟的煞笔电影，坚持在电影院看完后我问收回3D眼镜的“可以退票吗？”那人说“我说了不算啊”，这电影简直模仿抗日神剧啊，一弓箭射掉2架战斗机，其余的剧情一直在哔哔！

8. 100多分钟的煞笔电影，坚持在电影院看完后我问收回3D眼镜的“可以退票吗？”那人说“我说了不算啊”，这电影简直模仿抗日神剧啊，一弓箭射掉2架战斗机，其余的剧情一直在哔哔！

9. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。