地下アイドルの夢 Erlang(Beta)編（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

これは、B ランクの問題としてスキルチェックに出題されていた問題です。試しに解いてみましょう。
現時点では自力で正解することができない場合は、この問題を飛ばして次の問題に進んでください。
この問題の後に続く 3 つの問題に順番に取り組むことで、
この問題を解くために必要な知識や考えた方を身につけることができます。

「0 だった。今年の利益は 0。去年も 0。その前も、さらにその前も、ずっとずっと 0。来年こそは必ず……」

そう語るあなたの友人の地下アイドルをプロデュースすることになりました。

彼女のファンクラブには会員が N 人います。
彼女はファンクラブ会員限定のライブイベントを行いますが、ライブごとにある一定の開催費用がお客一人当たりにかかります。
彼女のファンクラブ会員はとても結束力が強く、どんなライブも開催すれば全員が必ず参加していました。
そこで全員から一人当たりの費用以上の入場料を徴収すれば赤字にはなりませんが、以前それを実行したところファンクラブ会員が激減してしまったため、現在は無料でライブを開催し、グッズを売ることで売上を得る戦略をとっています。

来年は全部で M 回のライブイベントを開催予定です。
ただし、すべてのライブを適当に開催すると赤字だらけになる可能性があるので、開催するライブを適切に選択する必要があります。
それぞれのライブごとに各ファンクラブ会員がもたらす損益の情報が存在します。損益とは過去の統計情報から得た、そのイベントにおいて各会員に対し予測されるグッズの購入額から、会員一人当たりのライブ開催費用を引いたものです。
ある会員があまりグッズを買わないと予測されると、この値は負になることがあります。
これはその会員が損失をもたらすことを意味しています。

例えば会員数 N = 3, イベント回数 M = 5 で、ライブイベントの情報が以下のとおりだったとしましょう。

ライブ＼会員	1	2	3
1	3	0	-2
2	1	5	1
3	-4	1	0
4	-1	-2	3
5	0	0	2

ライブ 1 は会員 1 が 3 円の利益をもたらし、会員 3 が 2 円の損失をもたらすことを表しています。その他も同様です。

この場合、開催したライブと、来年の彼女の損益の例を以下にいくつか示します。

開催したライブ	彼女が得る損益
1	1
3	-3
2 ,4	7
3 ,4	-3
1, 2, 3	5

また彼女が得る損益が負である場合は、その数の大きさと同じ数だけの損失が出るものとします。上記の表に記載の通り、もし彼女がライブ 3, 4 を開催した場合、彼女は来年 3 円の赤字になります。

さて、ファンクラブの会員数 N、ライブイベントの数 M、ライブごとの利益情報が与えられるので、あなたの友人のために、適切にライブを開催した場合に得られる来年の利益の最大値を求めてください。

ただし、N と M はそれぞれ値として 0 をとる可能性があることに注意してください。また、ライブをどのように開催しても得られる最大損益が負である場合、すなわち、必ず赤字になってしまう場合、それなら何もしないほうが良いということでライブイベントを実施しない、つまり損益 0 という処理にしてください。

入力される値: 入力は以下のフォーマットで与えられます。

N M
e_{1,1} e_{1,2} ... e_{1,N}
e_{2,1} e_{2,2} ... e_{2,N}
...
e_{M,1} e_{M,2} ... e_{M,N}

・1 行目には、ファンクラブの会員数 N、ライブイベントの数 Mが空白区切りで与えられます。

・2 行目以降の i+1 (1 ≦ i ≦ M) 行目には、ライブ i を開催した際に各会員から得る損益が空白区切りで与えられます。

・ここで、e_{i,j} (1 ≦ i ≦ M, 1 ≦ j ≦ N) はライブ i を開催した際に会員 j から得る損益を表します。

・ただし、N または M が 0 である場合は、e_{i,j} は入力されないことに注意してください。

・入力は合計 M+1 行からなり、末尾に改行を 1 つ含みます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 友人が得ることができる来年の利益の最大値を一行に出力してください。
最後は改行し、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・ 0 ≦ N ≦ 1000
・ 0 ≦ M ≦ 1000
・ -100 ≦ e_{i,j} ≦ 100

入力例1: 3 5
3 0 -2
1 5 1
-4 1 0
-1 -2 3
0 0 2

出力例1: 10

入力例2: 4 7
12 0 -19 -12
-7 -5 7 -17
7 -17 -10 10
-17 -4 -6 -12
-4 -9 -7 8
2 -15 -7 -7
0 -15 1 10

出力例2: 0

入力例3: 5 30
-70 -35 19 90 -8
-69 4 -54 5 -50
63 -81 -17 16 -28
93 -33 -21 78 11
6 -92 -90 -39 29
-61 -38 85 -56 47
-62 -74 61 4 -57
7 -58 19 96 99
89 -24 -78 -75 -6
97 11 -68 68 71
72 8 83 42 55
50 -6 11 59 -36
52 -97 -45 1 -69
14 9 -80 -78 38
-54 -33 78 -28 -6
15 91 67 20 -20
9 58 -16 95 -88
59 45 -11 59 84
99 -43 77 79 -37
-58 -80 -77 38 -91
-49 12 -47 -67 31
-20 62 -70 34 38
-90 -46 5 91 -63
5 79 80 -44 -61
60 68 29 -65 -36
-38 -83 -40 43 96
-20 -98 -71 6 85
95 15 36 -82 41
-74 -99 26 96 -70
-83 94 51 -36 -32

出力例3: 1714

問題一覧へ戻る