Obama and Gift
All submissions for this problem are available.
Barrack Obama is going to leave the white house soon. He has received a lot of gifts N in his tenure some of which he would like to take. But there are many gifts of each type and he would like to take at least one gift of each type.
The total type of gifts are 7. Each gift is represented by 3 integers :-
Type of the gift (1 to 7),
Price of the gift (p[i] ),
Quality of the gift (q[i]).
Obama can take gifts which sum to an amount less than P. You need to maximize the total quality of the gifts . The total quality is the quality of the gift with the lowest quality i.e If he takes gifts of quality 5,7,3,7,65,2,9 the total quality would be 2. You need to print the maximum total quality of the gifts that can taken by him.
It is compulsory to take one gift from each type. If no answer exists print "0"(without the quotes).
On the first line there are two integers N and P. In the next N lines there are 3 integers, type[i] , p[i] and q[i].
Output the total quality.
- 7 ≤ N ≤ 1000
- 1 ≤ type[i] ≤ 7
- 1 ≤ P ≤ 1000
- 1 ≤ p[i],q[i] ≤ P
Input: 8 54 7 1 3 5 8 2 2 4 8 6 8 13 1 13 12 4 5 1 3 2 7 3 13 5 Output: 1
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions