E. Give Me Your Candy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The candy store is running a special deal today! They have lined up $$$n$$$ candies in an array and are letting the first customer take home a contiguous subarray of the candies for free! Hearing this news, Suzuka and her friend Mizyu immediately raced to the candy store to take advantage. Suzuka, being the faster of the two, reaches the candy store first, and so she gets the deal.

To Suzuka, the $$$i$$$th candy has a tastiness of $$$a_i$$$. Since Suzuka finds some candies too sour to be enjoyable, $$$a_i$$$ can be negative. Obviously, the more tasty candies the better, so Suzuka wants to take a subarray that maximizes the sum of tastiness of candies in the subarray. However, as a consolation for her loss, Suzuka promises Mizyu the subarray she picks will include at least one piece of Mizyu's favorite type of candy, which she will share with Mizyu.

Suzuka wants to know, what is the greatest sum of tastiness of a subarray containing Mizyu's favorite candy that she can take?

Input

The first line of input contains a single integer $$$n\ (1\leq n\leq2\cdot10^5)$$$ — the number of candies in the array.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n\ (-10^9 \leq a_i\leq 10^9)$$$ — the tastiness of each candy.

The last line contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n\ (b_i\in\{0,1\})$$$ — denoting which candies are of Mizyu's favorite type, where $$$b_i=1$$$ means the $$$i$$$th candy is Mizyu's favorite, and $$$b_i=0$$$ means it is not. It is guaranteed at least one of the candies will be Mizyu's favorite type.

Output

Output a single integer, the greatest sum of tastiness of a subarray that contains at least one piece of Mizyu's favorite candy.

Examples
Input
4
-1 2 3 -4
1 1 0 0
Output
5
Input
5
10 -30 10 -100 50
0 1 0 1 0
Output
-10
Input
3
1000000000 1000000000 1000000000
1 1 1
Output
3000000000
Note

For the first test case, Suzuka can take the second and third candies corresponding to the subarray [2, 3] to obtain a total tastiness of 2+3=5.

For the second test case, Suzuka can take the first three candies corresponding to the subarray [10, -30, 10] to obtain a total tastiness of 10+(-30)+10=-10. Note she cannot take something like a subarray of just the last candy, because that does not contain Mizyu's favorite type of candy.