1157 LITTLE SHOP OF FLOWERS

時間制限:1000ミリ秒
メモリ制限:10000KB

問題

LITTLE SHOP OF FLOWERS
小さな花屋さんがウィンドウをきれいに飾りたがっています。

花屋はウィンドウに直列に並んだ花瓶に花を飾ることで評価を得ます。
どの花をどの花瓶に入れたら何点の評価が得られるか表で与えられます。

花瓶はウィンドウの中で左から右に直列にｗ個並び、一つの花瓶は一種類の花を入れることしかできません。
花の並び順は表の上から下へ決まっており、花瓶の並び順も表の左から右へ決まっています。
並べ替えることはできません。(原文図参照のこと)

順番をたがえずに左から順に並んだ花瓶に花を入れていってください。

どの花瓶にどの花を入れたら最高の評価が得られるか、その時の評価点を求めてください。
このとき使わない花瓶があっても問題はありません。

花瓶が左から花瓶1,花瓶2,花瓶3,花瓶4,花瓶5という並びで指定され、花がA,B,Cの並び順だとします。

花瓶２に花Aを入れ、花瓶３に花Bを入れ、花瓶5に花Cを入れる。
花瓶１に花Aを入れ、花瓶２に花Bを入れ、花瓶4に花Cを入れる。
等のように花瓶の順番も花の並び順も違えずに花を入れることで評価が決まります。
どの花瓶にどの花を入れたら何点という形で評価が決まり、その総計が答えとなります。

評価は表にある組み合わせの合計点となります。

原文のサンプルデータを解説します。
1番の花azaleasを2番の花瓶に入れて23点
2番の花begoniasを4番の花瓶に入れて10点
3番の花carnationsを5番の花瓶に入れて20点の合計53点がサンプルデータの解となります。

注意点
1番の花を5番に入れた後、2番の花を2番の花瓶に入れることはしてはいけません。
1番の花は必ず2番の花より左に飾らなければならないからです。
同様に2番の花は3番の花より左にある必要があります。

花の数F、花瓶の数Vが一行目に与えられます。
FとVは101以下です。
次にF行にわたってF*Vの表が与えられます
表はその花を花瓶に生けた時の評価点となっています。

順番をたがえず花瓶に花を入れていった時の最高スコアを算出してください。

3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

IOI 1999