No.561 東京と京都

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 239
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm / テスター : ei1333ei1333
6 ProblemId : 816 / 出題時の順位表

問題文

A君は仕事を全部で$N$日間行います。
仕事は東京と京都のどちらか好きなほうで毎日違った仕事をします。
東京の仕事で得られる収入は毎日異なります。
同じように京都の仕事で得られる収入も毎日異なります。

A君は東京と京都に家があり最初は東京にいます。
東京と京都間の移動のためには片道$D$円払わないといけません。
A君は毎日仕事前に東京と京都間を移動でき東京と京都のどちらかの仕事ができます。
仕事の収入と移動の支出を考慮してA君が$N$日間で増やせる金額を最大化しなさい。
なお、A君は$N$日間の間に資金が不足して移動できないことは無いとする。

入力

$N$ $D$
$T_1\ K_1$
$T_2\ K_2$
$\vdots$
$T_N\ K_N$

$N$はA君がする仕事の日数。$1 \le N \le 100=10^2$。
$D$は東京と京都間を移動するためのコスト(単位:円)。$1 \le D \le 10000000=10^7$。
$T_i$は$i$日目に東京で仕事をすると得られる収入(単位:円)。$1 \le T_i \le 10000000=10^7$。
$K_i$は$i$日目に京都で仕事をすると得られる収入(単位:円)。$1 \le K_i \le 10000000=10^7$。

出力

A君が$N$日間で増やした金額の最大値を1行で出力しなさい。
最後に改行してください。

サンプル

サンプル1
入力
2 10000
20000 32000
24000 23000
出力
45000

A君は2日間だけ仕事をします。
東京と京都の移動には10000円かかります。
1日目は東京の仕事で20000円もらえ、京都の仕事で32000円もらえます。
2日目は東京の仕事で24000円もらえ、京都の仕事で23000円もらえます。
A君は1日目に京都へ10000円で移動して仕事をすると22000円増やすことができます。
2日目はそのまま京都で仕事をすることで23000円増やすことができます。
A君は京都に移動したのち2日間とも京都で働いて45000円増やすことができました。

サンプル2
入力
2 10000
42000 50000
58000 56000
出力
100000

この場合A君は移動せず2日間とも東京で働いて100000円増やすことができます。

サンプル3
入力
3 10
42000 50000
58000 56000
40000 45000
出力
152970

移動のコストが10円と格安です。
A君は京都、東京、京都の順で仕事を選んで152970円増やしました。

サンプル4
入力
5 3000
10000 10000
20000 23000
30000 38000
44000 40000
54000 56000
出力
164000

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。