Oil Producing Nation

Interview

Time limit1sMemory limit512 MB

Summary

Pick a contiguous arc of districts on a circle that contains at least K threat districts, maximizing the sum of the A values.

Level: Medium6 of 10
Topics: Prefix sum, Sliding window, Array
Solved: No attempts yet

Problem

The United States of Jooddae, a true great power, works every day for world peace. To that end, USJ leader Oh Juwon has decided to contribute to keeping the peace today.

As you well know, the most important condition for a peaceful democracy is oil. You are preparing to seize a contiguous stretch of districts in Yunlac to extract oil.

Yunlac, the enemy of USJ, is divided into circular districts numbered from $1$ to $N$ . Some of these districts have threat groups.

Invading an enemy country to extract oil would draw the attention of other nations, so you have announced that you will occupy at least $K$ districts that have threat groups.

If you occupy district $i$ , you extract oil and gain $A_i$ in profit. If the cost of occupation is greater than the profit, the total profit may be negative.

How should you occupy the land so that Juwon gets the maximum profit?

Input

The first line contains the number of districts $N$ and the minimum number of threat groups $K$ that must be among the occupied districts.

The second line contains the integers $A_1, A_2, \dots, A_N$ , separated by spaces.

The third line contains the integers $B_1, B_2, \dots, B_N$ , separated by spaces. If $B_i$ is $0$ , district $i$ has no threat group. If $B_i$ is $1$ , it has one.

Output

Print the maximum profit Juwon can obtain.

Constraints

$1 \le K \le N \le 500\,000$
$-10^9 \le A_i \le 10^9$ ( $1 \le i \le N$ )
$B_i = 0$ or $1$ ( $1 \le i \le N$ )
There are at least $K$ indices $i$ with $B_i = 1$ .

Examples2

Example 1
Input
```
5 2
5 -2 -1 -5 1
1 0 1 1 0
```
Expected output
```
3
```
Example 2
Input
```
1 1
-1000000000
1
```
Expected output
```
-1000000000
```