Earn the Most

You are designing an algorithm that trades a single currency; each day you can buy one unit, sell one unit, or do nothing. rates[i] is the price on day i (a positive integer); strategy[i] is the action on day i: −1 buys, 0 holds (neither buys nor sells), and 1 sells. You are also given an even number k.

To improve performance, you may (but do not have to) modify strategy once as follows: choose exactly k consecutive elements, set the first half of them to 0, and set the second half to 1.

Profit is defined as the sum of all selling prices minus the sum of all buying prices, and it can be negative. Assume funds and holdings are always sufficient. Find the maximum profit you can obtain.

输入格式

The first line contains two integers n and k; the second line contains n integers rates; the third line contains n integers strategy. 2≤k≤n≤100000, k is even, 1≤rates[i]≤100000, strategy[i]∈{−1,0,1}.

输出格式

Output one integer: the maximum profit.

样例 1

输入：

6 4
2 4 1 5 10 6
-1 1 0 1 -1 0

输出：

18

样例 2

输入：

4 2
1 1 10 10
1 1 1 1

输出：

22

样例 3

输入：

4 4
3 1 4 1
-1 -1 -1 -1

输出：

5

样例说明

Example 1: rates=[2,4,1,5,10,6], strategy=[−1,1,0,1,−1,0], k=4. Without modification, the profit is −2+4+5−10=−3; choosing indices 2..5 changes strategy to [−1,1,0,0,1,1], for a profit of −2+4+10+6=18. Example 2: rates=[1,1,10,10] with every day selling gives an original profit of 22; any modification with k=2 turns a sell into a hold, so not modifying is optimal. Example 3: every day buys; choosing the whole array changes it to [0,0,1,1], for a profit of 4+1=5.