問題
ある日のプロ野球、某虎のチームVS某燕のチームの一戦。20-11というとても野球とは思えないスコアで虎チームが勝利した。
どう考えても11点取って大敗しているのは異常である。
燕チームの投手の致命的なところはスタミナのなさである。実力はあってもすぐにバテてしまう。
燕チームの監督は、この悲惨な投手のスタミナのなさを改善するために投手のスタミナを鍛えることにした。
チームの宿舎がある街にはN軒の焼肉店があり、1からN番までのいずれかの番号が被り無く付けられている。
番号が１番の焼肉店からスタートし、食べては次の焼肉店に走って移動を繰り返す。このとき、一度訪れた焼肉店は再び訪れることは出来ない。これを街にある全ての焼肉店で行ったら終了である。
これにより監督は肉によってスタミナを得られると考えたのだ。
しかし、うまくはいかなかった。
焼肉を食べるともちろんおなかはだんだん満腹になっていく。走ることでおなかはだんだん減っていく。
おなかが満腹の時、それ以上食べることは出来ない。そのときは肉によって得られるスタミナは0となってしまう。つまり、完食できなければスタミナを得ることは出来ない。焼肉を一部だけ食べても、スタミナは得られない。
焼肉店をどの順番で巡るかは決められていない。どのように焼肉店を巡れば最も肉によるスタミナが得られるかをあなたは調べてほしい。
なお、満腹で食べられない際はその店では何も食べずに次の店に行ってもよいが、完食できる際もその店で食べずに次の店に行ってもよい。だが、この場合その店には二度と訪れられないので注意すること。
入力
N U A S1 P1 d1~1 d1~2...d1~N S2 P2 d2~1 d2~2...d2~N . . . SN PN dN~1 dN~2...dN~N
１行目に空白区切りの整数で焼肉店の数N、お腹の限界値U、出発時点でのお腹のたまり具合Aが与えられる。お腹のたまり具合がUを超えるまでは焼肉を食べられるとする。
２行目からN行にかけて、焼肉店で得られるスタミナSとお腹のたまる量P,お腹の減る具合を表すdが与えられる。
di~jは、焼肉店iから焼肉店jに移動した際にお腹がdi~j減ることを表す。お腹のたまり具合は0より下にはならない。計算上下回る場合、お腹のたまり具合は0となる。
di~jとdj~iは同じ値とは限らない。
ただし、i=jの時、di~jは必ず0である。
出力
最も多くのスタミナを得られる焼肉店の巡り方をした際に、得られるスタミナを１行に出力する。
制約
全ての入出力ケースについて以下を満たす。
- 入力は全て正の整数である。
- 2≦N≦10
- 0≦A,Pi,di-j≦1000
- 1≦U≦1000
- 1≦Si≦10000
入出力例
入力例1
4 8 5 3 3 0 4 3 5 4 6 4 0 2 8 2 2 1 2 0 2 5 8 5 7 1 0
出力例1
11
解説
まず、現在店1にいる。このときに仮に店1で食事をした際は満腹度が3満たされるので、お腹の限界値の8を超えない。よって、店１で食事をすることは可能である。
しかし、ここで店1で食事をしないことが最適解である。
次に、店4に行く。現在の満腹度は5で、店1から店4に行く際に減る満腹度は5である。
よって、店４についた際の満腹度は5-5=0となる。
このとき、店4で食事をすることは可能である。なので、店4で食事をし、スタミナ5を得て、満腹度は8となる。
次に、店2へ移動する。店2についた際の満腹度は8-7=1である。
このとき、店2で食事をすることは可能である。なので、店2で食事をし、スタミナ4を得て、満腹度は7となる。
次に、店3へ移動する。店3についた際の満腹度は7-2=5である。
このとき、店3で食事をすることは可能である。なので、店3で食事をし、スタミナ2を得て、満腹度は7となる。ここで、全ての店を巡り終えたので店巡りを終える。
得られたスタミナの合計は11となり、これが最適解である。
参考程度に店1で食事をした際の最適な巡り方を解説する。
店1で食べ、店4へ移動。店4で食べ、店2へ移動。店2で食べず、店3へ移動。店3で食べて終える。こうすることでスタミナが10得られる。
これは店1で食べなかったときの最適解より劣るため、この入力例では店1で食べない方がよい。
入力例2
4 8 5 100 10 0 0 0 0 100 5 100 0 100 100 100 100 0 0 0 0 10000 10 0 0 0 0
出力例2
0
解説
テストケースによっては１度も焼肉が食べられない場合もある。
そのときは0を出力する。
入力例3
9 937 457 2406 324 0 166 272 224 160 109 264 173 109 2861 476 169 0 182 289 134 264 155 178 158 1797 470 169 156 0 144 204 230 152 228 239 2508 230 277 194 162 0 124 225 292 230 201 4148 419 126 172 280 119 0 178 247 159 261 3496 512 128 194 188 243 246 0 142 298 155 1028 266 126 127 270 173 285 298 0 100 166 1045 506 136 195 160 256 158 285 198 0 123 1965 533 250 130 165 263 162 209 224 212 0
出力例3
17384