Gift from Tyrion
All submissions for this problem are available.
Tyrion Lannister has planned a suitable reward for Podrick Payne his squire for saving his life in the battle of Blackwater Bay. He intends for Pod to have a good time in one of Petyr Baelish's several establishments in Kings Landing.
The establishment has several pleasures each with a pleasure value Pi. Each pleasure also has a fee of Ci. At the end of the day Tyrion wants Pod to have experienced at least P amount of pleasure in the most cheapest way.
You are Bronn a low born sell-sword of great skill and cunning, so Tyrion has asked you to figure out the minimum amount of money Pod should end up with and the maximum amount of pleasure he can have with it. It is guaranteed that Pod can enjoy at least P amount of pleasure in the establishment.
First line of the input contains T (1 <= T <= 25), the number of test cases
First line of each test case consists of 2 numbers N, P.
N is the number of pleasures in the establishment.
N lines follow each with a description of a pleasure.
The descriptions are of the form Ni Pi Ci
Ni - Pleasure's name (a sequence of characters)
Pi - Pleasure value of Ni
Ci - Fee charged for Ni
There is a blank line at the beginning of each test case.
For each test case you must output 2 numbers M and L.
M - minimum amount of money that is needed to have a pleasure of at least P.
L - Maximum pleasure Pod can have with the money M. (L >= P)
1 <= T <= 25
1 <= N <= 100
1 <= Pi <= 50
0 <= Ci <= 50
1 <= P <= 5000
1 <= |Ni| <= 25 (Each Ni has at most 25 characters which can be either uppercase or lowercase).
Each Ni is distinct.
ExampleInput 2 4 12 Alayaya 5 10 Chataya 7 20 Dancy 5 5 Petyr 50 50 2 15 Marei 15 15 Jayde 16 5 Output 25 12 5 16
|Time Limit:||0.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