No.561 東京と京都
タグ : / 解いたユーザー数 502
作問者 :
nmnmnmnmnmnmnm
/ テスター :
ei1333333
問題文
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
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。