#### Registered Users Only

Please login to view and utilize this feature.

## 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 3Output

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 10Output

3000

## Explanation

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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 10 | 10 | 0.5s | 32MB | Minimum |

2 | 20 | 10 | 0.5s | 32MB | Minimum |

3 | 30 | 10 | 0.5s | 32MB | Minimum |

4 | 40 | 10 | 0.5s | 32MB | Minimum |

5 | 0 | 2 | 0.5s | 32MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o money -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512