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