Problem Description

N piles of money are falling from the sky in a linear world made of T tiles :O

Wen Yuen is greedy and he wants to take it all for himself

However, he is fat, so he cannot move very quickly. He can only catch money on his tile.

He starts from tile 0 at time 0 and can move left, right or stay on the same spot each turn

He cannot move right beyond tile T-1 or move left beyond tile 0

$Ni falls on tile Nj at time Nk. Wen Yuen needs to be on tile Nj at time Nk in order to grab the money

What's the maximum amount of money Wen Yuen can make from this windfall of cash?

Input

A single line with the numbers N and T

This is followed by N lines each containing 3 integers, Ni,Nj and Nk

Constraints

N<=1,000

T<=10^18

Ni<=1,000,000

Nj<=T, Nk<=10^18

There will be no two cash drops at the same time

Output

A single integer describing the maximum amount of money Wen Yuen can get after all the money has fallen

Subtasks

Subtask 1 (10%) N=1, all other constraints apply

Subtask 2 (20%) N<=10, T<=10, Nk<=10, all other constraints apply

Subtask 3 (30%) N<=1000, T<=1000, Nk<=1000, all other constraints apply

Subtask 4 (40%) All above constraints apply

Sample Testcase 1

Input

2 5 
1000 2 1
9 2 3
Output
9

Explanation

Wen Yuen is too fat to get to tile 2 at time 1 as he can only move one tile at a time. However, he can catch the $9 from tile 2 at time 3 as he can get there by time 2

Sample Testcase 2

Input

3 10
1000 4 5
1000 4 12
2000 0 10
Output
3000

Explanation

Wen Yuen goes and grabs the $1000, then goes back to original position to grab his $2000