An Amazon delivery robot moves through
Each checkpoint has two lanes: lane
If the robot visits checkpoint
If the robot visits checkpoint
The robot must visit exactly one lane at every checkpoint from
Between two consecutive checkpoints, the robot may stay in the same lane for free, or switch to the other lane by paying a switching cost of
Your task is to find the maximum total reward the robot can collect after subtracting all switching costs.
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of checkpoints and the cost of switching lanes.
The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — the rewards in lane KaTeX can only parse string typed expression.
The third line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — the rewards in lane KaTeX can only parse string typed expression.
Print a single integer — the maximum total reward after subtracting switching costs.
Input
5 3
5 1 10 1 5
1 8 1 9 125One optimal path is lane KaTeX can only parse string typed expression, lane KaTeX can only parse string typed expression, lane KaTeX can only parse string typed expression, lane KaTeX can only parse string typed expression, lane KaTeX can only parse string typed expression.
The collected reward is KaTeX can only parse string typed expression.
The robot switches lanes KaTeX can only parse string typed expression times, so the switching cost is KaTeX can only parse string typed expression.
The final reward is KaTeX can only parse string typed expression.
Example 2:
Input
3 100
5 5 5
1 100 1102Switching is very expensive. The best choice is to stay in lane KaTeX can only parse string typed expression for all checkpoints and collect KaTeX can only parse string typed expression.
Example 3:
Input
1 50
7
2020There is only one checkpoint, so no switching is needed. The robot chooses lane KaTeX can only parse string typed expression and collects KaTeX can only parse string typed expression.