题目描述

从前，在海上有 $n$ 个岛屿，编号 $1$ 至 $n$。居民们深受洋流困扰，无法到达比自己当前所在岛屿编号更小的岛屿。经过数年以后，岛屿上的人数随着岛屿的编号递增（可能相等）。作为一名出色的旅行家（$\mathrm{RP}$ 学家），你想从 $1$ 号岛屿出发开启一次旅程，以获得更多的 $\mathrm{RP}$，因为受到海洋的洋流影响，你只能去到比当前岛屿编号更大的岛屿。因为你比较善良，你会在离开一个岛屿的时候将你的 $\mathrm{RP}$ 分散给岛民，具体地：你的 $\mathrm{RP}$ 会除以 $2$（用去尾法取整，或者说向零取整）（当你的 $\mathrm{RP}$ 小于零时，岛民也依旧要帮你分担，毕竟你们已经建立起了深厚的友谊)。

第 $i$ 号岛屿有 $T_{i}$ 人，但是你很挑剔，每次你从 $j$ 号岛屿到达 $i$ 号岛屿时，你只会在到达的岛屿上做 $T_{i} \times T_{j}$ 件好事（一件好事可以获得 $1$ 点 $\mathrm{RP}$ )。

唯一不足的是，由于你在岛上住宿，劳民伤财，你会扣除巨量 RP，第 $i$ 号岛屿的住宿扣除 $F_{i}$ 点 $\mathrm{RP}$。

注意: 将离开一个岛屿时，先将 $\mathrm{RP}$ 扣除一半，再扣除住宿的 $\mathrm{RP}$，最后在新到达的岛屿上做好事，增加 $\mathrm{RP}$。离开 $1$ 号岛屿时需要扣除在 $1$ 号岛屿住宿的 $\mathrm{RP}$，当到达这段旅程的最后一个岛屿上时，要做完好事，行程才能结束，也就是说不用扣除在最后到达的岛屿上住宿的 $\mathrm{RP}$ 。

你因为热爱旅行（RP），所以从 $1$ 号岛屿开始旅行，初始时你有 $0$ 点 $\mathrm{RP}$。你希望选择一些岛屿经过，最终选择一个岛屿停下来，求最大的 $\mathrm{RP}$ 值是多少?

输入格式

输入的第一行包含一个数 $n$，表示岛屿的总数。

第二行包含 $n$ 个整数 $T_{1},T_{2},\cdots,T_{n}$，表示每个岛屿的人口数。

第三行包含 $n$ 个整数 $F_{1},F_{2},\cdots,F_{n}$，表示每个岛屿旅馆损失的 $\mathrm{RP}$。

输出格式

输出一个数，表示最大获得的 $\mathrm{RP}$ 值。

3
4 4 5
1 10 3

19

5
969 980 1013 1016 1021
888423 945460 865822 896150 946615

246172

提示

【样例说明】

从一号岛屿直接走到三号岛屿最优，初始 $0$ 点 $\mathrm{RP}$，扣除一半取整变成 $0$ 点。扣除在一号节点住宿的 $1 \mathrm{RP}$，在三号岛屿做好事产生 $4 \times 5=20$ 点 $\mathrm{RP}$。最终得到 $19$ 点 $R P$ 。

【评测用例规模与约定】

对于 $20 \%$ 的评测用例，$1 \leq n \leq 15$;

对于 $70 \%$ 的评测用例，$1 \leq n \leq 5000$;

对于所有评测用例，$1 \leq n \leq 5\times10^5,1 \leq T_{i} \leq 20000,1 \leq F_{i} \leq 2\times 10^8$。给定的 $T_{i}$ 已经按照升序排序。

建议使用 64 位有符号整数进行运算。

蓝桥杯 2020 第三轮省赛 AB 组 J 题。

Upd.2024.7.13 已添加hack数据