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.