Problem 3B. RP++

时间限制：0.5s

空间限制：64MB

题目背景

一天小季发现了一个刷题网站，点开这个网站的题库，发现一共有 \(n\) 道题目。在这个网站中，做对每道题目都可以获得一定的rp值；当然，这其中肯定有一些题目是小季不会做的，做这些题目不会让小季获得任何rp值(因为做不出来)。小季想从中选3道题目来做来获得尽可能高的rp值，不过选3道获得最高rp值的题目没有意思，小季想加点限制...

题目描述

以 \(x_1, x_2, x_3...,x_n\) 代表做每道题可以获得的rp值，\(y_1,y_2,y_3...,y_n\)代表每道题小季会不会做第 \(i\) 题，用 \(0\) 和 \(1\) 表示， \(0\) 代表不会做， \(1\) 代表会做；那么小季每道题可以获得的rp值就可以用 \(x_i * y_i\) 来表示。

现在小季要从中选出三道题 \(x_a, x_b, x_c\) ，满足以下条件：

• \(a < b < c\)
• \(x_a \le x_b \le x_c\)

小季想知道满足以上条件时最高可以获得的rp值，即你需要找到一个三元组 \([a,b,c]\) 在满足上述条件时 \(x_a*y_a + x_b * y_b + x_c * y_c\) 的值最大。

输入格式

输入包括三行，第一行一个整数 \(n\) ，代表题目数量；

第二行 \(n\) 个整数 \(x_1, x_2, x_3, .. , x_n\) 代表每道题可以获得的rp值；

第三行 \(n\) 个是 \(0\) 或 \(1\) 的整数 \(y_1, y_2, y_3, ..., y_n\) 代表对于每道题小季是否会做。

输出格式

输出一个整数，代表满足条件的可以获得的最大rp值。如果找不到满足条件的三元组，则输出 -1。

样例1

输入

6
10 20 30 40 50 10
0 0 1 1 0 1

输出

70

解释

选取第3,4,5道题获得的rp值是最高的。

样例2

输入

5
50 40 30 20 10
1 1 1 1 1

输出

-1

解释

不存在满足条件的三元组。

样例3

输入

3
10 20 30
0 0 0

输出

0

数据范围

对于 \(60\%\) 的数据，\(1 \le n \le 100\);

对于 \(100\%\) 的数据，\(1 \le n \le 2000\), \(0 \le x_i \le 100\).