Problem Description

A train starts from the starting point with an initial height of $0$ and travels to the right at a constant speed of $1$ (i.e., it moves 1 unit of horizontal distance per second). The departure time of the train is a given constant $D$ (i.e., it departs from the starting point at time $D$). Track construction can begin at time $0$.

There are $n$ track segments to be constructed, numbered $1$ to $n$. Each track segment $i$ is described by three integer parameters:

• Length $L_i$: a positive integer, representing the horizontal distance of the track segment.
• Height change $S_i$: an integer, representing the change in height after the train travels through this track segment. If $S_i > 0$, it is an uphill segment (height increases by $S_i$); if $S_i < 0$, it is a downhill segment (height decreases by $|S_i|$).
• Construction time $T_i$: a positive integer, representing the time required to construct this track segment.

You need to determine the traveling order of these segments (the order in which the train passes through them) and the construction order (the order in which they are built).

Constraints

1. Construction order constraint: Only one track segment can be constructed at a time, and construction cannot be interrupted. For the $k$-th segment in the traveling order, it must be completed before the train arrives at the starting point of that segment, i.e., its completion time $\le$ the train's arrival time at the starting point of that segment.
2. Non-negative height: At any moment during the journey, the height of the train must not fall below $0$.
3. Final height zero: After traveling through all $n$ track segments, the train's height must be exactly $0$.

Objective

Among all traveling orders and construction plans that satisfy the above conditions, minimize the maximum height reached by the train during the journey. If no feasible solution exists, output $-1$.

Input Format

The first line contains two integers $n, D$.

The next $n$ lines each contain three integers $L_i, S_i, T_i$.

Output Format

Output an integer representing the minimum possible maximum height, or $-1$ if no solution exists.

Examples

Sample Input 1

2 5
2 1 3
1 -1 2

Sample Output 1

1

Explanation: Both track segments can be completed before departure (total construction time $3+2=5$). Traveling uphill first and then downhill results in a maximum height of $1$.

Sample Input 2

7 20
3 2 3
4 3 4
2 -1 2
3 -2 3
2 1 2
1 -2 1
2 -1 2

Sample Output 2

3

Explanation: By following the traveling order $2,4,1,3,5,7,6$ (i.e., track segment 2, track segment 4, track segment 1, track segment 3, track segment 5, track segment 7, track segment 6), the height never exceeds $3$ throughout the journey, and this value is optimal.

Sample Input 3

7 20
3 2 3
4 3 4
2 -1 2
3 -2 3
2 1 2
1 2 1
2 -1 2

Sample Output 3

-1

Explanation: It is impossible to achieve a final height of zero, so no solution exists.

Constraints

• $1 \leq n \leq 20$
• $1 \leq D \leq 10^{10}$
• $1 \leq L_i, T_i \leq 10^{10}$
• $|S_i| \leq 10^{10}$