Description You are a theif sneaking into a house that contains N items. You carry a bag and want to steal some valuable items from the house. Unfortunately, your bag can hold at most K kilograms. As a smart theif, you know exactly the value Vi and the weight Wi of each item. Since your bag is not strong enough to carry over the limit of K (the sum of weight Wi you carry must be less then K). What is the highest value you can carry out from this house? Input The first line contains two integers N and K, representing the number of items in the house and how much can the bag hold. Each of the following N lines contain two integers Vi and Wi, describing the value and weight of the i-th item. It is guaranteed that: Os Vi, Wis 10 For test case #1-9:15 NS 20,0 SKS 103 For test case #10:15 NS 100,0 SKS 103 Output Print the most value the thief can get. (you need to print a newline ''n' right following your answer) For the sample test case, we can choose the third item (6,3) and the fifth (5.4) item. The maximum value the thief can get would be 11. Sample Input Download 57 34 53 63 43 54 Sample Output Download 11 Description You are a theif sneaking into a house that contains N items. You carry a bag and want to steal some valuable items from the house. Unfortunately, your bag can hold at most K kilograms. As a smart theif, you know exactly the value Vi and the weight Wi of each item. Since your bag is not strong enough to carry over the limit of K (the sum of weight Wi you carry must be less then K). What is the highest value you can carry out from this house? Input The first line contains two integers N and K, representing the number of items in the house and how much can the bag hold. Each of the following N lines contain two integers Vi and Wi, describing the value and weight of the i-th item. It is guaranteed that: Os Vi, Wis 10 For test case #1-9:15 NS 20,0 SKS 103 For test case #10:15 NS 100,0 SKS 103 Output Print the most value the thief can get. (you need to print a newline ''n' right following your answer) For the sample test case, we can choose the third item (6,3) and the fifth (5.4) item. The maximum value the thief can get would be 11. Sample Input Download 57 34 53 63 43 54 Sample Output Download 11