Chef and Shop
All submissions for this problem are available.
Read problems statements in Russian also.
Chef likes shopping, and especially he likes to buy oranges. But right now he is short of money. He has only k rubles. There are n oranges. The i-th one costs costi rubles and has weight equal to weighti. Chef wants to buy a set of oranges with the maximal possible weight. Please help him, and tell him this weight.
The first line of the input contains an integer T denoting the number of test cases. The first line of each test case contains two numbers n and k. The following n lines contain two numbers costi and weighti respectively.
For each test case, output a single line containing maximal weight among all the affordable sets of oranges.
- 1 ≤ T ≤ 250
- 1 ≤ n ≤ 10
- 1 ≤ k ≤ 100000000
- 1 ≤ weighti ≤ 100000000
- 1 ≤ costi ≤ 100000000
Input: 2 1 3 2 2 3 4 2 1 2 2 3 5 Output: 2 5
Subtask 1 (30 points): All the oranges' weights equals to 1.
Subtask 2 (30 points): N = 5
Subtask 2 (40 points): See the constraints
|Tags||cakewalk, combinatorics, furko, ltime08|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.