| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12698 | Steal the most value Quiz |
|
Description
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))
}
Input
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 :
- 1 ≤ N ≤ 10, 0 ≤ K ≤ 103
- 0 ≤ Vi, Wi ≤ 103
- K ≤ ΣWi (The total value of all items will equal or greater to K)
Output
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.