E問題 - Kougakubu M@ster

実行時間制限: 2sec / メモリ制限: 1024MB

問題文

Tsurugiくんは\(N\)日間の間精進をします。
1日に3つの問題がレコメンドされ、その中から1つを選んで解きます。あるいは、1日休みます。

はじめ、Tsurugiくんの体力は\(H\)です。

Tsurugiくんは\(i\)日目に問題\(j\)を解くと、\(P_{ij}\)の得点を得、体力を\(A_{ij}\)消費します。休むことにした場合、その日は問題を解くことができないかわりに体力を\(R\)回復します。 ただし、同じ日に複数の問題を解くことはできません。

Tsurugiくんの体力が負の値になった時点で、\(N\)日が終了していなかったとしてもTsurugiくんは精進をやめてしまいます。

Tsurugiくんの体力がはじめて負の値になるか、もしくは\(N\)日が終わった時点での得点の合計として考えられる最大値を求めてください。

制約

• \(1 \leq N \leq 200\)
• \(1 \leq H,A_{ij} \leq 2000\)
• \(0 \leq R \leq 200\)
• \(1 \leq P_{ij} \leq 2 \times 10^5\)
• 入力はすべて整数で与えられる。

入力

入力は以下の形式で標準入力から与えられる。

N H R
P_00 A_00 P_01 A_01 P_02 A_02
P_10 A_10 P_11 A_11 P_12 A_12
...
P_N0 A_N0 P_N1 A_N1 P_N2 A_N2

出力

Tsurugiくんの体力がはじめて負の値になった時点か\(N\)日が終了した時点での得点の合計として考えられる最大値を出力せよ。

入力例1

3 20 2
10 8 8 7 15 10
15 7 18 8 32 14
15 6 17 5 22 13

出力例1

55

1日目に問題3、2日目に問題2、3日目に問題3を解くことで得点を最大化できます。