SOLDIER - Help the soldier

no tags 

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 this 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.


hide comments
one_piece_: 2018-06-30 21:54:41

greedy works just fine .I got AC 0.00 with greedy

da_201501181: 2017-05-26 12:11:02

Limits are different than mentioned in the statement..!!

Shubham Jadhav: 2017-05-25 11:10:50

O(T*N) DP :)

Nallagatla Manikanta: 2016-08-09 15:43:24

accepted with dp+greedy

gs255: 2016-07-16 04:46:30

Greedy solution passed?

hazefully: 2016-05-01 08:06:03

WA because of the ambiguity of the problem statement as others have complained, the soldier must buy 6 items which means that if you are given less types than 6 "there is no answer". Good luck. :)

minhthai: 2016-02-16 05:04:26

why code limit :(

Raunak jain: 2015-08-04 19:28:33

incomplete problem statment!

Last edit: 2015-08-15 16:06:00
Medo: 2015-07-27 18:34:36

Something is weird in the Judge I/O. Same code gives NZEC error in JAVA when using a Scanner, but AC in C++. ( Same input reading/output formatting). There are still accepted solutions in JAVA, but code this in C/C++ if you can.

i_am_looser: 2015-06-04 08:49:41

Don't use fast I/O. will give tle. Don't know why.


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