The A-levels are finally OVER!! Mr Panda has decided to go out to celebrate with his friends and they have arrived at a lavish buffet restaurant. The buffet restaurant contains two extremely long tables containing N plates of food, conveniently labelled 1,2...N, evenly spaced out along each table.
Mr Panda starts out at the plate 1 of either table 1 or 2 and walks down the tables to collect food and fill his hungry stomach. He collects food from plates 1,2,...N in order as he walks down the tables. Due to the extremely long queue behind him, he only has time to take one piece of food from plate i on table 1 OR table 2 and then has to move on.Each piece of food on plate i gives him a satisfaction of Pi1 or Pi2 points if taken from table 1 or 2 respectively. Furthermore, due to his extreme excitement, if he takes food from table 1 in row i then takes food from table 2 in row i+1 or vice versa, he will drop food while crossing over to the other table and lose K points of satisfaction.
Help Mr Panda gain the maximum number of satisfaction points after walking down the buffet tables once so he can enjoy his buffet :D
The first line of the input contains two integers N and K.
The second line of input contains N integers separated by spaces. The ith integer represents Pi1.
The third line of input contains N integers separated by spaces. The ith integer represents Pi2.
The output should only contain 1 integer, the maximum number of satisfaction points Mr Panda can get after walking down the buffet tables once.
For all testcases, 0 ≤ Pi1 , Pi2 , K ≤ 109
Subtask 1(8%): 0 < N ≤ 106, K=0
Subtask 2(14%): 0 < N ≤ 20
Subtask 3(26%): 0 < N ≤ 1000
Subtask 4(52%): 0 < N ≤ 106
Subtask 5(0%): Sample
5 1 1 3 3 4 10 2 1 5 0 5
21
Explanation: Start at table 2 and take food. Cross to table 1, take food, cross back to table 2, take food, cross back to table 1, take the last two pieces of food. Total satisfaction points gained is 2+(3-1)+(5-1)+(4-1)+10=21
| Subtask | Score |
|---|---|
| 1 | 0 |
| 2 | 8 |
| 3 | 14 |
| 4 | 26 |
| 5 | 52 |