SOLDIER - Help the soldier

Igor, a famous Russian soldier, must go to war in Afghanistan (we are in late 80’s). His superiors allowed him to buy himself his equipment. So, he must buy 6 items: helmet, bulletproof vest, trousers, boots, tunic and a firearm. This items are represented with numbers from 1 to 6. There are N (6 < N < 101) items of these 6 types. Each item is characterized by its price p[i] (in rublas) and is quality q[i]. Igor has T (0 < T < 1001) rublas and he wants to maximize the total quality of his equipment. The total quality is the quality of the item with the lowest quality. Help him.

Input

On the first line there are two integers N and T. On the lines 2 ... N+1 there are 3 integers, type[i] (from 1 to 6) p[i] and q[i]. (0 < p[i], q[i] < T )

Output

Output the total quality.

Example

Input:
7 53
5 8 2
2 4 8
6 8 13
1 13 12
4 5 1
3 2 7
3 13 5

Output:
1

Note

If there is no answer, output 0.

There can be less than 6 types of items.

[ Edited by EB ]

Warning: Some input files are incomplete and broken.


Added by:Pripoae Toni
Date:2008-09-14
Time limit:0.109s
Source limit:2048B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Original

hide comments
2014-06-27 09:48:36 zicowa
i request to the setter do not add such problems which include this much ambiguity it is quite difficult to solve such problem and even if there exists ambiguity then either correct it or mention it in comments thanx:P
2014-06-27 09:46:49 zicowa
and here is something about the problem that it essentially asked you to find the minimum quality when item of each type are considered it means it is neccessary that each type of item must be include and then find the minimum .
2014-06-27 09:45:17 zicowa
hey i get to know either the test data for this problem is wrong or week here is a proof one submitted solution is giving this 10 for this test case but actual answer is 0 youu can verify your own.
6 60
1 10 10
2 10 10
3 10 10
4 10 10
5 10 10
6 12 10
2014-06-27 07:26:08 zicowa
i think constraints allowed me to apply dp with a upperbound of O(n*(tmax)) O(10^5)
2014-06-27 07:24:40 zicowa
I first thought to apply greedy but that is failing my own test case and i thought of applying DP which i think is sufficient to solve this problem but i dont know why i am getting WA any critical test case any one of you may have ??
2014-06-27 06:54:26 zicowa
as one said question is incomplete i too feel this .it is not mentioned in the problem whether it is neccessay to buy items of each and every type if this is the case then for all the cases in which items are of less than 6 types answer is simply zero .so, please do mention such kinds of things in the statement itself!!
2014-05-28 19:12:28 paras meena
Simple Greedy No need to DP
2014-04-17 19:57:06 SHOBHIT SAXENA
Input test cases contain invalid items numbers. <1 or >6
Got Segsev many times.
Ignoring those cases i got AC.
2014-03-18 04:20:27 Daniel Barboza Franco
There is something strange with the input. Be careful with the method you are using to parse/split the input. For those using Java, Scanner will do the job.

Last edit: 2014-03-18 04:21:04
2014-02-18 10:13:52 Rishav Goyal
@problem setter : problem is incomplete in itself!!!
1. are we supposed to buy maximum number of items with unique item of each type.
2. what if there exist 2 possible sets having same maximum quality but two different lowest quality items.
3. problem says "must buy" 6 items.

what ???

please describe it properly. Thanks in advance.

Last edit: 2014-02-18 12:19:12
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.