Island Journey: Maximizing RP

You are given n islands numbered from 1 to n. The population on the islands is non‐decreasing, i.e. the number of people on island i is given by \( T_i \) and they satisfy \( T_1 \le T_2 \le \cdots \le T_n \). In addition, each island i has an associated accommodation cost \( F_i \). You start your journey on island 1 with \( \mathrm{RP} = 0 \) points. Being a compassionate traveler (an RP collector), you want to travel to an island with a larger index at each step in order to eventually stop at one island. However, due to strong ocean currents you can only travel forward from island j to island i if \( i>j \>.

The journey follows these rules:

1. If you are at island \( j \) with current \( \mathrm{RP} \), when leaving the island, first you update \( \mathrm{RP} \) by dividing it by \( 2 \) with truncation toward zero. In other words, the new value is \( \text{trunc}\left(\frac{\mathrm{RP}}{2}\right) \).
2. Then, you subtract the lodging cost \( F_j \) for island \( j \) (note that when leaving island 1 you must also pay the cost \( F_1 \)).
3. Upon arriving at island \( i \), you perform good deeds. Specifically, you do exactly \( T_i \times T_j \) good deeds, each granting you 1 RP, so you add \( T_i \times T_j \) to your RP.

Note: At the final island of your journey, you do not pay the lodging cost, but you must perform the good deeds upon arrival to finish the journey.

Your task is to select a sequence of islands (starting at island 1 and moving only to islands with larger indices) and finish the journey at some island such that the resulting RP is maximized. It is allowed to end the journey immediately at island 1 (i.e. no moves) where the RP will remain \( 0 \). Compute the maximum achievable RP.

The transition when traveling from island \( j \) to island \( i \) (with \( i>j \)) can be formulated as:

[ \mathrm{RP}_i = \text{trunc}\left(\frac{\mathrm{RP}_j}{2}\right) - F_j + T_i \times T_j, ]

with the starting value \( \mathrm{RP}_1 = 0 \). Your answer is the maximum expression value among all islands for which you can finish the journey.

inputFormat

The first line contains an integer \( n \) (the number of islands).

The second line contains \( n \) space-separated integers \( T_1, T_2, \dots, T_n \) representing the population of each island (in non-decreasing order).

The third line contains \( n \) space-separated integers \( F_1, F_2, \dots, F_n \) representing the accommodation cost on each island.

outputFormat

Output a single integer: the maximum achievable \( \mathrm{RP} \) after finishing the journey.

sample

1
10
5

0