Description

Xiao Ming got a dance pad game program called Dance. In each round, the game outputs $N$ moving "arrows", numbered $1$ to $N$, and the corresponding scores are $S_1, S_2, \ldots, S_N$. If you hit arrow $i$, you gain $S_i$ points; otherwise, you lose $S_i$ points.

Additionally, the game has an accumulation reward: if the accumulated number of hits reaches $T$ upon hitting arrow $i$, you receive a bonus of $B_i$ points, and the accumulated count is reset to $0$ and restarted.

For example: $N = 6, T = 3$, and the sequences $S$ and $B$ are {1, 2, 3, 4, 5, 6} and {0, 0, 4, 7, 9, 10}, respectively. If Xiao Ming hits all arrows, the score is: $(1+2+3+4) + (4+5+6+10) = 35$.

Xiao Ming is a Dance expert and can hit any arrows he chooses. However, he finds that for given $N, T, S, B$, hitting all arrows does not necessarily yield the highest score. He wants to know the maximum possible score. Can you help him compute the maximum obtainable total score?

Input Format

The first line contains two integers $N$ and $T$.

The second line contains $N$ integers, the scores of $S$.

The third line contains $N$ integers, the bonuses of $B$.

Output Format

Output one integer, the maximum obtainable score.

6 3
1 2 3 4 5 6
1 1 1 20 1 1

39

Hint

Sample explanation:

Skip the first arrow and lose 1 point, then hit 3 arrows to gain 9 points and receive an additional 20 points in bonus, then hit 2 more arrows, for a total of 39 points.

Constraints:

• For 20% of the testdata, $0 \le N, T \le 100$.
• For 100% of the testdata, $0 \le N, T \le 5000$.
• The sequences $S$ and $B$ each contain $N$ numbers, and all scores are integers in $[0, 10000]$.

Translated by ChatGPT 5