Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dp

implementation

two pointers

*1200

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Lecture Sleep

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYour friend Mishka and you attend a calculus lecture. Lecture lasts *n* minutes. Lecturer tells *a*_{i} theorems during the *i*-th minute.

Mishka is really interested in calculus, though it is so hard to stay awake for all the time of lecture. You are given an array *t* of Mishka's behavior. If Mishka is asleep during the *i*-th minute of the lecture then *t*_{i} will be equal to 0, otherwise it will be equal to 1. When Mishka is awake he writes down all the theorems he is being told — *a*_{i} during the *i*-th minute. Otherwise he writes nothing.

You know some secret technique to keep Mishka awake for *k* minutes straight. However you can use it only once. You can start using it at the beginning of any minute between 1 and *n* - *k* + 1. If you use it on some minute *i* then Mishka will be awake during minutes *j* such that and will write down all the theorems lecturer tells.

You task is to calculate the maximum number of theorems Mishka will be able to write down if you use your technique only once to wake him up.

Input

The first line of the input contains two integer numbers *n* and *k* (1 ≤ *k* ≤ *n* ≤ 10^{5}) — the duration of the lecture in minutes and the number of minutes you can keep Mishka awake.

The second line of the input contains *n* integer numbers *a*_{1}, *a*_{2}, ... *a*_{n} (1 ≤ *a*_{i} ≤ 10^{4}) — the number of theorems lecturer tells during the *i*-th minute.

The third line of the input contains *n* integer numbers *t*_{1}, *t*_{2}, ... *t*_{n} (0 ≤ *t*_{i} ≤ 1) — type of Mishka's behavior at the *i*-th minute of the lecture.

Output

Print only one integer — the maximum number of theorems Mishka will be able to write down if you use your technique only once to wake him up.

Example

Input

6 3

1 3 5 2 5 4

1 1 0 1 0 0

Output

16

Note

In the sample case the better way is to use the secret technique at the beginning of the third minute. Then the number of theorems Mishka will be able to write down will be equal to 16.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/08/2023 18:08:10 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|