You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

还记得若干年前那段互相比较《克罗地亚狂想曲》的分数的日子吗？

题目描述

E.Space 喜欢打音游。

但是他技术不好，总是拿不到全连（Full Combo）。

现在他面前有一份乐谱，乐谱的其中一段有 $n$ 个连续的单键音符。

相邻两个音符的到来时间均相等，我们可以认为第 $i$ 个音符会在第 $i$ 个时刻到来。

点击一个音符，E.Space 需要一段准备时间来进行移动手指之类的操作。由于音符的位置和周围情况不同，点击每个音符的准备时间也不同。

在一个音符的准备时间内，E.Space 没法做到去点击其它音符，但是不同音符的准备时间范围可以互相重叠。形式化地，令第 $i$ 个音符的准备时间为 $ti$ 个单位时间，那么如果 E.Space 选择去点击第 $i$ 个音符，那么他就没法点击所有到来时刻在 $(i − ti, i + ti)$ 中的音符。

为了获得更高的分数，E.Space 还计算了每个音符的性价比。一个音符的性价比等于点击这个音符得到的分数除以 E.Space 点击它所需要的准备时间。

E.Space 就不指望全连了，他只是想让你帮他计算一下他最多可以得到多少分数。

格式

输入格式

第一行一个正整数 $n$ 。

第二行 $n$ 个正整数，第 $i$ 个正整数表示 $ti$ 。

第三行 $n$ 个正整数，第 $i$ 个正整数表示第 $i$ 个音符的性价比 $ai$。

输出格式

一行一个正整数，表示 E.Space 可能达到的最高分数。

样例

5
2 3 2 1 2
3 1 2 9 4

18

样例 1 解释

E.Space 可以选择点击第 1, 3, 5 个音符，分数为 2 × 3 + 2 × 2 + 2 × 4 = 18 。

数据范围

$ti ≤ n，ai\le 10^9$