Problem Description

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

Input

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.

Output

The output should only contain 1 integer, the maximum number of satisfaction points Mr Panda can get after walking down the buffet tables once.

Limits

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

Sample Input

5 1
1 3 3 4 10
2 1 5 0 5

Sample Input

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