Anipero 2012

D: アニペロ2012

アニペロサマーライブ，通称アニペロは，さまざまなアニメソングアーティストたちが集結する，日本国内最大のアニメソングライブイベントである．アニソンが大好きな2D君は，昨年に引き続き，今年もアニペロに行くことにした．

彼は，アニペロを楽しむために，すでにサイリウムをm本購入している．サイリウムとは，折ると化学反応で光るスティックである．リズムに合わせてサイリウムを振ることで，ライブを盛り上げることができ，自分の満足度も上昇する．今回，彼が購入した全てのサイリウムは，次のような性質を持つ．

• サイリウムは，折ってから時間が経過するにつれ暗くなっていき，10分で光を失う．
• 折ってから5分の間は，非常に明るい（以下，「レベル2」と呼ぶ）．
• 折ってから5分経過した後は，少し暗くなる（以下，「レベル1」と呼ぶ）．
• 振っても振らなくても，光を失うスピードは変わらない．

2D君は，限られたサイリウムを曲によってうまく使い分けることで，今年のアニペロでどれだけの満足度を得られそうか，以下の問題を考えることにした．

彼は，ライブ中に流れるであろう曲をn曲予想している． 各曲の長さは，全て5分である． n曲は，連続で流れ続け，曲と曲の間は，0分と考えてよい． 各曲には，以下の3つのパラメータが与えられる．

• ある曲に対して，レベル2を1本だけ振ったときに増える満足度
• ある曲に対して，レベル1を1本だけ振ったときに増える満足度
• ある曲において，1本も振らないときに増える満足度

サイリウムを振ったからといって，満足度が増えるとは限らない． 振ったら逆に会場の雰囲気を乱して，満足度が減る場合もある． 振らない場合も，同様のことが言える．

サイリウムは，以下のルールに従って使用しなければならない．

• 曲が始まる時点でのみ折ることができ，一度に何本でも折ることができる．サイリウムを折るのにかかる時間は無視してよい．
• 1曲で最大8本同時に振ることができる．
• 複数のサイリウムを振る際，以下の式により加算する満足度を計算する．
• (レベル1の本数)×(レベル1の1本あたりの満足度)＋(レベル2の本数)×(レベル2の1本あたりの満足度)
• 1本もサイリウムを振らない場合は，1本も振らない場合の満足度だけを加算する．
• 一度振ると決めたサイリウムは，1曲が終了するまで持ち替えることはできない．
• サイリウムは，振らずに置いておくことができる．また，サイリウムを全て使いきる必要はない．

2D君は，ライブの曲予想までは済ませたが，それだけで疲れてしまって，問題を解く気になれなかった． あなたの仕事は，彼の代わりに，今年のライブで得られそうな最大満足度を求めるプログラムを書くことである．

Input

ライブの予想曲リストに対する満足度情報が入力される．

1行目に，ライブで歌われる曲数n (1 <= n <= 50)と，ライブ開始時に2D君が持っている新品のサイリウムの数m (0 <= m <= 50)がスペース区切りで入力される． 続くn行では，1行ずつ1曲の情報が入力される． i番目(1 <= i <= n)の曲情報は，

• 曲iに対して，レベル2のサイリウムを1本振ったときの満足度a_i
• 曲iに対して，レベル1のサイリウムを1本振ったときの満足度b_i
• 曲iにおいて，サイリウムを1本も振らないときの満足度c_i

がスペース区切りで入力される(-100 <= a_i, b_i, c_i <= 100)．

Output

ライブ終了時の2D君の最大満足度の予想を1行に出力せよ． 最大満足度がマイナスになることもあるので，注意すること． 行の最後には，改行を出力すること．

Sample Input 1

1 5
2 3 8

Sample Output 1

10

Sample Input 2

2 10
2 2 20
2 3 -10

Sample Output 2

44

Sample Input 3

3 10
5 1 9
-3 2 1
1 11 0

Sample Output 3

102

Note

Commentary

 

---