No.561 Tokyo and Kyoto
タグ : / 解いたユーザー数 481
作問者 :
nmnmnmnmnmnmnm
/ テスター :
ei1333333
Problem Statement
A-kun will work for a total of $N$ days.
Each day he does a different job, in whichever of Tokyo or Kyoto he prefers.
The income from the job in Tokyo differs from day to day.
Likewise, the income from the job in Kyoto differs from day to day.
A-kun has homes in both Tokyo and Kyoto, and is initially in Tokyo.
To travel between Tokyo and Kyoto, he must pay $D$ yen each way.
Each day before work, A-kun can travel between Tokyo and Kyoto, and he can do either the job in Tokyo or the job in Kyoto.
Taking into account the income from the jobs and the travel expenses, maximize the amount of money A-kun can gain over the $N$ days.
Note that A-kun will never be unable to travel due to a lack of funds during the $N$ days.
Input
$N$ $D$ $T_1\ K_1$ $T_2\ K_2$ $\vdots$ $T_N\ K_N$
$N$ is the number of days A-kun works. $1 \le N \le 100=10^2$.
$D$ is the cost of traveling between Tokyo and Kyoto (in yen). $1 \le D \le 10000000=10^7$.
$T_i$ is the income from working in Tokyo on day $i$ (in yen). $1 \le T_i \le 10000000=10^7$.
$K_i$ is the income from working in Kyoto on day $i$ (in yen). $1 \le K_i \le 10000000=10^7$.
Output
Output in one line the maximum amount of money A-kun can gain over the $N$ days.
Print a newline at the end.
Sample
Sample 1
Input
2 10000 20000 32000 24000 23000
Output
45000
A-kun works for only 2 days.
Traveling between Tokyo and Kyoto costs 10000 yen.
On day 1, the job in Tokyo pays 20000 yen and the job in Kyoto pays 32000 yen.
On day 2, the job in Tokyo pays 24000 yen and the job in Kyoto pays 23000 yen.
If A-kun travels to Kyoto for 10000 yen on day 1 and works there, he can gain 22000 yen.
On day 2, by staying and working in Kyoto, he can gain 23000 yen.
By traveling to Kyoto and then working in Kyoto on both days, A-kun was able to gain 45000 yen.
Sample 2
Input
2 10000 42000 50000 58000 56000
Output
100000
In this case, A-kun can gain 100000 yen by not traveling and working in Tokyo on both days.
Sample 3
Input
3 10 42000 50000 58000 56000 40000 45000
Output
152970
The travel cost is a bargain at just 10 yen.
A-kun chose jobs in the order Kyoto, Tokyo, Kyoto, and gained 152970 yen.
Sample 4
Input
5 3000 10000 10000 20000 23000 30000 38000 44000 40000 54000 56000
Output
164000
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。