Hello, administrator, I find this problem's data is too weak.Sometime before, I submitted my code to this problem, and got AC.Today, I sudden to realize my mistake, and I back to check my answer.Oh, my god, I had so stupid mistake.To my suprise, I had AC.So I think the problem's data is too weak.Please generate more strong input..

Hi!

There seem to be many *accepted* solutions here that do not really try all possible combinations. These do *NOT* solve this problem, as some have pointed out correctly, this is a knapsack type of problem and unless going through all 2^n combinations of n numbers, you cannot find the optimal answer. It is clear, that the test data are too weak indeed!!!