004 - アップダウン

時間制限 5 秒 / メモリ制限 256 MB / 得点 100 / x 0 /

TLE
5sec
MLE
256MB
得点
100
ジャッジデータのoutの方を作るソースが間違っててとても申し訳ないです。リジャッジしました。また、入出力例3は制約を満たしていませんがジャッジデータは制約を満たしています。入出力例4の出力を修正しました。
原因として想定していた解法(メモ化再帰)でジャッジデータのoutを作るにあたりdpテーブルを必要な分より小さく確保したままメモ化再帰をしていたことが原因です。元に戻した結果MLEすることが判明しました。
これを想定していた解法でも解けるように制約を修正し、ジャッジデータを作り直します。すみませんでした。

問題

つくば市に住むジョーイ君は最近曲作りにはまっています。
ジョーイ君はN個のフレーズをすでに用意しています。各フレーズには盛り上がり度Gと基準となるフレーズの速さTが決められており、１つ前のフレーズの速さとの差の絶対値とフレーズの盛り上がり度を掛け合わせたものがそのフレーズの最終的な盛り上がり度となります。
また、全てのフレーズの最終的な盛り上がり度の総和が曲の盛り上がり度となり、ジョーイ君はこの曲の盛り上がり度を出来る限り大きくするように各フレーズの速さを調節します。(フレーズを流す順番はすでに決まっています。)
各フレーズの速さは、フレーズiの基準となる早さをTiとしたとき、Ti-RiからTi+Riまでに調節することが出来ます。
ただし、速さは必ず整数にしなければいけません。
また、条件として、各フレーズの、前のフレーズの速さとの差の絶対値の総和がPを超えてはいけません。
あなたはジョーイ君が曲の盛り上がり度が最大になるように各フレーズの速さを調節した場合、曲の盛り上がり度がどのくらいになるのかを調べることにしました。

入力

N P
T1 R1 G1
T2 R2 G2
.
.
.
TN RN GN

１行目にフレーズの数Nと、フレーズの速さの差の絶対値の総和の上限Pが整数で空白区切りで与えられる。
2行目からはN行にかけて、i(1≦i≦N)番目に使われるフレーズの情報が与えられる。Tiはi番目のフレーズの基準となるフレーズの速さを、Riはそのフレーズの速さを調節できる範囲を、Giはそのフレーズの盛り上がり度を表している。

出力

ジョーイ君が出来るだけ曲の盛り上がり度が最大になるように曲を作った場合の、曲の盛り上がり度を１行に出力する。

制約

全ての入出力ケースについて以下を満たす。

  • 1≦N≦100
  • 1≦P≦3000
  • 1≦Ti-R≦Ti≦Ti+R≦50
  • 1≦Gi≦1000
  • 必ず条件を満たした曲を少なくとも１つは作ることが出来る。

入出力例

入力例1

3 10
5 0 2
1 0 6
3 0 4

出力例1

32

解説

この入出力例はすべてのフレーズの速さの調節できる範囲が0のため、作れる曲のパターンは１つのみとなります。
この時、曲の盛り上がり度はこのようにして求まります。
１つめのフレーズの速さと２つめのフレーズの速さの差の絶対値は|5-1|=4となり、これに２つめのフレーズの盛り上がり度の6を掛けた値の24が２つめのフレーズの最終的な盛り上がり度になります。
２つめのフレーズの速さと３つめのフレーズの速さの差の絶対値は|1-3|=2となり、これに３つめのフレーズの盛り上がり度の4を掛けた値の8が２つめのフレーズの最終的な盛り上がり度になります。
絶対値の総和は4+2=6となり、10以下なので、この時条件を満たしています。
曲の盛り上がり度は24+8=32となり、これが答えとなります。

入力例2

3 10
5 3 2
1 0 6
3 2 4

出力例2

54

解説

この入出力例はすべてのフレーズの速さの調節できる範囲が0のため、作れる曲のパターンは複数あります。その中で最も曲の盛り上がり度が大きくなるようにするには次のようにします。
この時、曲の盛り上がり度はこのようにして求まります。
１つめのフレーズの速さを8、２つめのフレーズの速さを1、３つめのフレーズの速さを4とします。 １つめのフレーズの速さと２つめのフレーズの速さの差の絶対値は|8-1|=7となり、これに２つめのフレーズの盛り上がり度の6を掛けた値の42が２つめのフレーズの最終的な盛り上がり度になります。
２つめのフレーズの速さと３つめのフレーズの速さの差の絶対値は|1-4|=3となり、これに３つめのフレーズの盛り上がり度の4を掛けた値の12が２つめのフレーズの最終的な盛り上がり度になります。
絶対値の総和は7+3=10となり、10以下なので、この時条件を満たしています。
曲の盛り上がり度は42+12=54となり、これが答えとなります。

入力例3

1 1000
25 24 1000

出力例3

0

解説

フレーズが１つしかないとき、前のフレーズとの差は１つもないため、0となります。

入力例4

10 233
20 6 840
15 1 202
26 2 586
27 19 614
14 9 956
24 9 690
44 0 901
24 13 386
33 5 226
33 14 691

出力例4

125986