You are a theif sneaking into a house that contains N-items.
Each item contains its own value(Vi) and weight(Wi).
Your target is to steal at least K values.
Since you are too lazy to hold too many items, so you want to take as light as possible.
What is the lightest weight you need carry out from this house with at least K value?
(ps: the sum of value you steal cannot be less then K)
Hint: You can try to use recursive function to get whether each item is taken or not.
For example:
Function getval()
{
if(end condition) return
return(getval(take the item),getval(not take the item))
}
The first line contains two intergers N (the number of items in the house)and K(how much value you need carry out).
The first line contains two integers N and K, representing the number of items in the house and how much value you need to carry out.
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 :
willPrint the lightest weight the thief need to carry.
(you need to print a newline '\n' right following your answer)
For the sample test case, we can choose (40,3) (30,2) (30,3) to steal. The lightest weight we need to carry is 8.