蒙蒙的箱子

题目背景

蒙蒙一共有$n$个物品依次在地上排列，每个物品都有一个价值$a_i$。有部分物品有箱子，而有些物品没有箱子。而一个箱子至多装一件物品。若一件物品用箱子装起来了，则可以获得$a_i$的价值，否则不能获得价值。蒙蒙有点懒，但又不是很懒，她可以把一个物品的箱子至多向左或向右移动一个位置，这样以来，原来箱子中装的物品便没有箱子了，而移动到的新物品有箱子了。一个箱子至多移动一次但蒙蒙可以移动多次箱子，求最后的价值和的最大值。

题目描述

给定两个序列$a_i$与$b_i$。

其中$a_i$表示第$i$个物品的价值，而$b_i$描述了第$i$个位置是否有箱子，$b_i=1$表示有，反之表示无。

每个箱子至多向左或向右没有箱子的位置移动一次，当一个物品有箱子时会带来价值$a_i$，否则不会带来价值，求最大价值和。

输入格式

请注意输入文件名。

第一行一个整数$n$，表示序列长度。

第二行共$n$个整数$a_i$，含义见上。

第三行共$n$个整数$b_i$，含义见上。

输出格式

请注意输出文件名。

你需要输出一个整数，表示最大价值和。

样例 #1

样例输入 #1

3
1 2 3
0 1 0

样例输出 #1

3

样例 #2

样例输入 #2

3
1 3 1
1 0 1

样例输出 #2

4

样例 #3

样例输入 #3

我们提供了一组额外的数据，请参考box文件夹。

样例输出 #3

我们提供了一组额外的数据，请参考box文件夹。

提示

数据范围：

对于10%的数据，我们保证$1<=n<=20$。

对于30%的数据，我们保证$1<=n<=1000$。

对于另外10%的数据，我们保证$\sum_{i=1}^n b_i<=20$。

对于100%的数据，我们保证$1<=n<=10^6,0<=a_i<=10^9,0<=b_i<=1$。