存在一个长度为 $n$ 的数组 $a$，由独立且均匀随机生成的整数 $a_i$ ($1 \le a_i \le 10^9$) 组成。同时，存在一个长度为 $n$ 的数组 $b$，由独立且均匀随机生成的整数 $b_i$ ($0 \le b_i \le 1$) 组成。Laura 想要从数组 $a$ 中删除若干个（可以为零个）元素，然后取数组 $b$ 中长度与之匹配的前缀，并最大化得到的数组内积（即 $\sum_{i=1}^m a_i \cdot b_i$，其中 $m$ 是删除后剩余元素的个数）。请帮助她实现这一目标。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 4 \cdot 10^5$) —— 数组 $a$ 和 $b$ 的长度。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le 10^9$) —— 数组 $a$ 的元素。

第三行包含 $n$ 个整数 $b_1, \dots, b_n$ ($0 \le b_i \le 1$) —— 数组 $b$ 的元素。

保证在所有测试点中，除了第一个测试点（即样例中的第一个）外，所有的数字 $a_i$ 和 $b_i$ 都是在对应范围内独立且均匀随机生成的。

保证总测试点数量不超过 20 个。

输出格式

输出一个整数 —— 在从数组 $a$ 中删除若干元素后，可能得到的最大内积。

样例

输入 1

8
1 4 6 5 1 2 3 6
1 0 1 0 1 0 0 1

输出 1

15

输入 2

4
843693973 430360361 788359887 531088030
1 1 1 0

输出 2

2163141890

说明

在第一个样例中，我们可以从 $a$ 中删除第 1、第 5 和第 6 个元素。结果将等于数组 $[4, 6, 5, 3, 6]$ 和 $[1, 0, 1, 0, 1]$ 的内积，即 $4 \cdot 1 + 6 \cdot 0 + 5 \cdot 1 + 3 \cdot 0 + 6 \cdot 1 = 15$。