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


hide comments
distructo: 2020-12-30 10:53:50

This problem is broken I got AC with a greedy solution, which offcourse doesn't work always

horro: 2020-07-01 19:52:08

simple dp!!

gol_d_roger: 2020-03-29 07:40:41

AC in one go! Use DP. Plain and simple. No sorting , greedy,etc etc...

aayush_b1999: 2019-08-06 22:08:29

getting wrong on 9th help!!!!

solved now

Last edit: 2019-08-06 22:29:22
joydip007x: 2018-12-30 13:51:06

a) handle this case (type[i]>6) {avoid ;}
b) p[i] , q[i] <1100
c) Don't use fast I/O

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?


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