2014
01-04

# Difficulty control

LL is very sensitive to the difficulty of ACM problems. He can assign each problem a positive integer from [1,10000000] to denote its difficulty ( although he has only ACed about 1000 problems ^_^ ). Now, there are N problems in his mind. He want to choose some of them to hold a contest and the total difficulty of all problems in the contest is as near as possible to M.

For each case, the first line is two positive integers N and M (1<=N<=26). Followed by N lines. Each line contains the problem’s ID ( a single capital letter ) and its difficulty.

For each case, the first line is two positive integers N and M (1<=N<=26). Followed by N lines. Each line contains the problem’s ID ( a single capital letter ) and its difficulty.

3 10
A 4
B 12
C 8

2
A C

Hint
"A C", "B" and "C" all reach the request. So, the answer is "A C", which comes earliest in lexicography order.


1. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法

2. 你的理解应该是：即使主持人拿走一个箱子对结果没有影响。这样想，主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率，但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3