問題文

ゆきこさんの車は距離 1 進むごとに燃料を 1 消費します。 ゆきこさんはこの車に乗って、長さ $L$ の道を運転してスーパーに行きます。 ゆきこさんの車にははじめ、車にはガソリンが 満杯の $V$ だけ入っています。 道の上には $N$ 箇所のガソリンスタンドがあり、そこではガソリンを補給できます。

各ガソリンスタンド $i$ には、位置（スタート地点からの距離）$x_i$、補給できる燃料の量 $v_i$、補給にかかる費用 $w_i$ が決まっています。 ゆきこさんはこのガソリンスタンドに来ると、 量に依存しない固定の 費用 $w_i$ を支払うことで、 ガソリンを最大 $v_i$ 補充することができます。 ただし、燃料タンクの中身が最大量を超えるような補充をすることはできません。また、ゆきこさんに帰りはありません。

ゆきこさんがスーパーに行くのに必要な費用の最小値を求めてください。

追記

2020-04-24 21:44 座標が減る方向には移動できません。

2020-04-24 21:45 同じガソリンスタンドで費用を複数回支払って燃料を複数回補充することはできません。

2020-04-24 22:07 ガソリンと燃料は、同一のものを指します。

2020-04-24 22:09 出力で、燃料の最小値を出力するように書いていましたが、費用の最小値に修正しました。

2020-04-24 22:17 「燃料タンクの中身が最大量を超えるような補充をすることはできません。」というのは、今の残量がxで、v_iだけ補充をするとき、補充後の残量はmin(V,x+v_i)になるということです。

入力

$NVL$
$x_0{v}_0{w}_0$
$\dots$
$x_{N-1}{v}_{N-1}{w}_{N-1}$

1 行目に、ガソリンスタンドの数 $N$、燃料タンクの容量（＝はじめの燃料の量）$V$、 コースの全長 $L$ が空白区切りで与えられます。 続く $N$ 行に、ガソリンスタンドの情報が与えられます。$i$ 番目のガソリンスタンドの情報は、 所在地のスタートからの距離 $x_i$、補給できるガソリンの量$v_i$、補給するのに必要な費用 $w_i$ の 3 つからなり、これらが空白区切りで与えられます。

入力は以下の制約を満たします。

• $1\le N\le 2000$
• $1\le V\le 2000$
• $1\le L\le {10}^9$
• $0\le x_0\le x_1\le \cdots \le x_{N-1}\le L$
• $0\le v_i\le {10}^9$
• $0\le w_i\le {10}^9$

出力

ゴールするのに必要な費用の最小値を 1 行で出力してください。 ただし、ゴールすることができないときには '-1' を出力してください。

サンプル

3 5 10
2 4 2
3 3 3
8 2 4

7

2 5 10
0 20 0
10 20 0

-1