#### Registered Users Only

Please login to view and utilize this feature.

## 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 P_{i1} or P_{i2} 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 *i*^{th} integer represents P_{i1}.

The third line of input contains N integers separated by spaces. The *i*^{th} integer represents P_{i2}.

## 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 ≤ P_{i1} , P_{i2} , K ≤ 10^{9}

Subtask 1(8%): 0 < N ≤ 10^{6}, K=0

Subtask 2(14%): 0 < N ≤ 20

Subtask 3(26%): 0 < N ≤ 1000

Subtask 4(52%): 0 < N ≤ 10^{6}

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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 8 | 10 | 1s | 32MB | Minimum |

2 | 14 | 5 | 1s | 32MB | Minimum |

3 | 26 | 5 | 1s | 32MB | Minimum |

4 | 52 | 10 | 1s | 32MB | Minimum |

5 | 0 | 1 | 1s | 32MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o buffet -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512