問題描述

一列火車從起點出發，初始高度為 $0$，以速度 $1$ 勻速向右行駛（即每秒前進 $1$ 單位水平距離）。火車的出發時間為給定的常數 $D$（即在時間 $D$ 時從起點出發）。從時間 $0$ 開始就可以建造軌道。

共有 $n$ 段軌道需要建造，編號 $1$ 到 $n$。每段軌道 $i$ 由三個整數參數描述：

• 長度 $L_i$：正整數，表示該段軌道的水平距離。
• 高度變化 $S_i$：整數，表示火車行駛完該段軌道後的高度變化量。若 $S_i > 0$ 則為上坡（高度增加 $S_i$），若 $S_i < 0$ 則為下坡（高度減少 $|S_i|$）。
• 建造時間 $T_i$：正整數，表示建造該段軌道所需的時間。

你需要決定這些軌道的 行駛順序（即火車經過它們的先後次序）以及 建造順序（即建造它們的先後次序）。

約束條件

1. 建造順序約束：同一時間只能建造一段軌道，且建造過程中不能中斷。對於行駛順序中的第 $k$ 段軌道，它必須在火車到達該段起點之前建造完成，即其建造完成時間 $\le$ 火車到達該段起點的時間。
2. 高度非負：火車在行駛過程中的任意時刻，高度不能低於 $0$。
3. 終點高度為零：在行駛完所有 $n$ 段軌道之後，火車的高度必須恰好為 $0$。

目標

在所有滿足上述條件的行駛順序和建造方案中，最小化火車行駛過程中的最大高度。如果不存在任何滿足條件的方案，輸出 $-1$。

輸入格式

第一行兩個整數 $n, D$。

接下來 $n$ 行，每行三個整數 $L_i, S_i, T_i$。

輸出格式

一個整數，表示最小可能的最大高度；若無解則輸出 $-1$。

範例

範例輸入 1

2 5
2 1 3
1 -1 2

範例輸出 1

1

解釋：可在出發前完成兩段軌道的建造（建造總時間 $3+2=5$）。行駛時先上坡後下坡，最大高度為 $1$。

範例輸入 2

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

範例輸出 2

3

解釋：按照行駛順序 $2,4,1,3,5,7,6$（即軌道2、軌道4、軌道1、軌道3、軌道5、軌道7、軌道6）行駛，整個過程高度不超過 $3$，且該值是最優的。

範例輸入 3

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

範例輸出 3

-1

解釋：無法使終點高度為零，因此無解。

數據範圍

• $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}$