Currency Trading — Sell k Consecutive Days

The price on each day is rates[i]>0, and the strategy is −1 to buy one unit, 0 to do nothing, and 1 to sell one unit. Funds and holdings are guaranteed to always be sufficient, and the profit is Σrates[i]×strategy[i], which may be negative. You may keep the original strategy or modify it once: choose a contiguous window of length exactly k, set its first k/2 items to 0 and its last k/2 items to 1, leaving everything outside the window unchanged. Find the maximum profit.

输入格式

The first line contains n k, the second line contains n rates, and the third line contains n strategy values. Original SIG ranges: 2≤n≤100000, 1≤rates[i]≤1000, strategy[i]∈{−1,0,1}. k is even and 2≤k≤n, supplemented from the identical problem eBay023 where the SIG text was truncated; that page's nums.length is normalized to the common array length n.

输出格式

Output the maximum profit as one integer; you may leave the strategy unchanged, but a negative profit must not be treated as 0, and you may not modify more than once.

样例 1

输入：

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

输出：

18

样例 2

输入：

2 2
1 1
1 1

输出：

2

样例 3

输入：

2 2
1 1000
0 0

输出：

1000

样例说明

In the original example, the original profit is −3, and the three modification windows give profits −4, 13, and 18, so the answer is 18. selling all of [1,1] without modification gives 2, while a forced modification gives only 1. In the third added example, with prices [1,1000], strategy [0,0], and k=2, selling in the second half gives 1000. The original text's "may change" supports an optional single modification, and its NOTE rules out inventory and funding constraints. SIG's own price upper bound of 1000 is kept rather than replaced by a larger bound from other companies' versions of the same problem.