Accepted Necklace
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 103 Accepted Submission(s) : 44
Problem Description
I have N precious stones, and plan to use K of them to make a necklace for my mother, but she won't accept a necklace which is too heavy. Given the value and the weight of each precious stone, please help me find out the most valuable necklace my mother will accept.<br>
Input
The first line of input is the number of cases. <br> For each case, the first line contains two integers N (N <= 20), the total number of stones, and K (K <= N), the exact number of stones to make a necklace. <br> Then N lines follow, each containing two integers: a (a<=1000), representing the value of each precious stone, and b (b<=1000), its weight. <br> The last line of each case contains an integer W, the maximum weight my mother will accept, W <= 1000. <br>
Output
For each case, output the highest possible value of the necklace.
Sample Input
1 <br>2 1 <br>1 1 <br>1 1 <br>3
Sample Output
1
Source
HDU男生专场公开赛——赶在女生之前先过节（From WHU）