Quiz Show

Time limit5sMemory limit128 MB

Summary

For N ordered quiz questions, choose right or wrong answers to maximize score: correct answers earn coins and points, hitting M coins gives a bonus, wrong answers reset coins and cost points.

Level: Hard8 of 10
Topics: Dynamic programming, Array, Math, Simulation
Solved: No attempts yet

Problem

Dohyun is participating in a TV quiz show. He must solve N questions in order, from question 1 to question N.

Dohyun already knows the correct answer to every question, so for each question he may choose whether to answer correctly or intentionally answer incorrectly.

If he answers a question correctly, he gains one coin and earns that question's base score. If he answers incorrectly, he loses all coins he currently has and his score decreases by that question's base score.

If answering a question correctly makes his coin count reach M, he also earns that question's bonus score, then returns all coins so that his coin count becomes 0.

Find the maximum score Dohyun can obtain.

Input

The first line contains the number of questions N and the number of coins M required to receive a bonus score. (1 ≤ N, M ≤ 500,000)

The second line contains the base scores of questions 1 through N in order. The third line contains the bonus scores of questions 1 through N in order.

Each base score is a nonnegative integer at most 1,000, and each bonus score is a nonnegative integer at most 10,000.

Output

Output the maximum score Dohyun can obtain.

Examples5

Example 1
Input
```
5 3
150 20 30 40 50
0 0 0 0 250
```
Expected output
```
500
```
Example 2
Input
```
5 3
1 2 3 16 14
7 0 20 33 66
```
Expected output
```
98
```
Example 3
Input
```
5 5
1 2 3 4 5
0 0 0 2 5
```
Expected output
```
20
```
Example 4
Input
```
5 3
1 2 3 4 5
0 0 0 2 5
```
Expected output
```
16
```
Example 5
Input
```
4 4
998 1 11 23
9998 1 11 23
```
Expected output
```
1056
```