Problem Description

Long ago, there were $n$ islands on the sea, numbered from $1$ to $n$. The residents were troubled by ocean currents and could not reach any island with a smaller number than the island they were currently on. After several years, the population on the islands increased with the island number (ties are allowed). As an excellent traveler (an $\mathrm{RP}$ scholar), you want to start a trip from island $1$ to gain more $\mathrm{RP}$. Due to the ocean currents, you can only travel to islands with a larger number than your current island.

Because you are kind, when you leave an island you will distribute your $\mathrm{RP}$ to the residents. Specifically, your $\mathrm{RP}$ will be divided by $2$ and rounded down (i.e., truncated toward zero). (When your $\mathrm{RP}$ is negative, the residents still have to share the burden, because you have built a deep friendship.)

Island $i$ has $T_i$ people. However, you are picky: each time you travel from island $j$ to island $i$, you will only do $T_i \times T_j$ good deeds on the island you arrive at. (Each good deed gives $1$ point of $\mathrm{RP}$.)

The only downside is that staying on an island costs a lot. Staying on island $i$ deducts $F_i$ points of $\mathrm{RP}$.

Note: When leaving an island, first halve your $\mathrm{RP}$, then deduct the lodging $\mathrm{RP}$ cost, and finally do good deeds on the newly arrived island to increase $\mathrm{RP}$. When leaving island $1$, you must deduct the lodging cost on island $1$. When you arrive at the last island of your trip, you must finish doing the good deeds before the trip ends; that is, you do not need to deduct the lodging cost on the final island you arrive at.

You love traveling ($\mathrm{RP}$), so you start from island $1$. Initially you have $0$ points of $\mathrm{RP}$. You want to choose some islands to visit and finally stop at one island. Find the maximum possible $\mathrm{RP}$ value.

Input Format

The first line contains an integer $n$, the total number of islands.

The second line contains $n$ integers $T_1, T_2, \cdots, T_n$, the population of each island.

The third line contains $n$ integers $F_1, F_2, \cdots, F_n$, the $\mathrm{RP}$ loss for lodging on each island.

Output Format

Output one number, the maximum $\mathrm{RP}$ value you can obtain.

3
4 4 5
1 10 3

19

5
969 980 1013 1016 1021
888423 945460 865822 896150 946615

246172

Hint

Sample Explanation

Going directly from island $1$ to island $3$ is optimal. Starting with $0$ points of $\mathrm{RP}$, halving and truncating still gives $0$. Deduct $1 \mathrm{RP}$ for lodging on island $1$. On island $3$, doing good deeds produces $4 \times 5 = 20$ points of $\mathrm{RP}$. Finally you get $19$ points of $R P$.

Constraints and Notes

For $20\%$ of the testdata, $1 \leq n \leq 15$.

For $70\%$ of the testdata, $1 \leq n \leq 5000$.

For all testdata, $1 \leq n \leq 5 \times 10^5$, $1 \leq T_i \leq 20000$, $1 \leq F_i \leq 2 \times 10^8$. The given $T_i$ are already sorted in nondecreasing order.

It is recommended to use 64-bit signed integers for calculations.

Lanqiao Cup 2020, Round 3 Provincial Contest, AB Group, Problem J.

Upd.2024.7.13 Hack data has been added.

Translated by ChatGPT 5