Help with "Long and Random" Problem

(https://vjudge.net/problem/QOJ-15112)

Problem Statement

Long and Random

Input file: standard input Output file: standard output Time limit: 6 seconds Memory limit: 1024 mebibytes

There is an array a of length n consisting of independent uniformly random integers a_i (1 ≤ a_i ≤ 10^9). Also, there is an array b of length n consisting of independent uniformly random integers b_i (0 ≤ b_i ≤ 1). Laura wants to erase some (possibly zero) elements from array a, then take the prefix of array b with the matching length, and maximize the resulting dot product of the arrays (i.e. sum of a_i * b_i for i from 1 to m). Help her to do that.

Input

In the first line, there is one integer n (1 ≤ n ≤ 4 * 10^5) — the length of the arrays a and b.

In the second line, there are n integers a_1, ..., a_n (1 ≤ a_i ≤ 10^9) — the elements of the array a.

In the third line, there are n integers b_1, ..., b_n (0 ≤ b_i ≤ 1) — the elements of the array b.

It is guaranteed that in all tests, except for the first one (from the examples), all numbers a_i and b_i are generated independently from a uniform distribution over the corresponding ranges.

It is guaranteed that there are no more than 20 tests in total.

Output

Print one number — the maximum possible dot product after erasing some elements from array a.

Examples

Example 1:

Input => 8 1 4 6 5 1 2 3 6 1 0 1 0 1 0 0 1

Output => 15

Example 2:

Input => 4 843693973 430360361 788359887 531088030 1 1 1 0

Output => 2163141890

Note

In the first example, we can erase the first, fifth and sixth elements from a. The result will be equal to the dot product of the arrays [4, 6, 5, 3, 6] and [1, 0, 1, 0, 1] which equals 4*1 + 6*0 + 5*1 + 3*0 + 6*1 = 15.

Question

I've been trying to solve this problem but I'm stuck on the approach. Can anyone help me understand the solution or provide an editorial?