Dance Mat Maximum Score

Xiaoming has obtained a dance mat game program called Dance. In each round, the game shows N arrows in order (numbered from $1$ to $N$). Each arrow has an associated score $S_i$. If you step on (hit) the i-th arrow correctly, you gain $S_i$ points; otherwise, you lose $S_i$ points.

In addition, there is a cumulative bonus mechanism: every time the total number of successful steps (since the last bonus) reaches $T$, and if this occurs on the i-th arrow that was hit, you will receive an extra bonus of $B_i$ points. Once the bonus is given, the hit counter resets to $0$, and the process continues.

For example, if $N=6$, $T=3$, with \( S = \{1, 2, 3, 4, 5, 6\} \) and \( B = \{0, 0, 4, 7, 9, 10\}, \) and if Xiaoming hits all arrows, then the score calculation is as follows:

[ \begin{array}{lcl} \text{First bonus:} &:& 1+2+3+4 = 10 \ \text{Second bonus:} &:& 4+5+6+10 = 25 \ \text{Total score:} &:& 10 + 25 = 35 \end{array} ]

Your task is to help Xiaoming determine the maximum achievable score if he can choose for each arrow whether to hit it or miss it. Note that when you miss an arrow, you lose $S_i$ points, and the hit counter does not increase. When you hit an arrow, the counter increases by $1$; if the counter becomes $T$, then in addition to the $S_i$ points for that arrow, you also gain the bonus $B_i$, and the counter is reset to $0$.

Input and Output details are given below.

inputFormat

The first line contains two integers N and T ($1 \leq N \leq 10^5$, $1 \leq T \leq N$), representing the number of arrows and the bonus threshold, respectively.

The second line contains N integers: $S_1, S_2, \ldots, S_N$, where $S_i$ is the score for the i-th arrow.

The third line contains N integers: $B_1, B_2, \ldots, B_N$, where $B_i$ is the bonus score if the cumulative hit count reaches T at the i-th arrow.

outputFormat

Output a single integer representing the maximum score Xiaoming can obtain.

sample

6 3
1 2 3 4 5 6
0 0 4 7 9 10

35