Polo the Penguin and the Test
All submissions for this problem are available.
Read problems statements in Russian here
Polo, the Penguin, has a lot of tests tomorrow at the university.
He knows that there are N different questions that will be on the tests. For each question i (i = 1..N), he knows C[i] - the number of tests that will contain this question, P[i] - the number of points that he will get for correctly answering this question on each of tests and T[i] - the amount of time (in minutes) that he needs to spend to learn this question.
Unfortunately, the amount of free time that Polo has is limited to W minutes. Help him to find the maximal possible total number of points he can get for all tests if he studies for no more than W minutes.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains the pair of integers N and W, separated by a space. The following N lines contain three space-separated integers C[i], P[i] and T[i] (i = 1..N).
For each test case, output a single line containing the answer to the corresponding test case.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 100
- 1 ≤ C[i], P[i], T[i] ≤ 100
- 1 ≤ W ≤ 100
Input: 1 3 7 1 2 3 2 3 5 3 3 3 Output: 11
Example case 1. The best choice is to learn the first and the third questions and get 1*2 + 3*3 = 11 points.
|Tags||cook39, dynamic-programming, easy, witua|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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.