Description

Jimmy has recently become obsessed with a game called Block Elimination. The rules are as follows: $n$ colored blocks are arranged in a row. Blocks of the same color that are contiguous form a region (if two adjacent blocks have the same color, then these two blocks belong to the same region). To simplify the problem, we represent the number of blocks in each contiguous region of the same color by a single number.

For example, 9 122233331 is represented as

4
1 2 3 1
1 3 4 1

During the game, you may choose any one region to remove. Suppose this region contains $x$ blocks; then you gain $x^2$ points. After removing a region, the remaining blocks close up from both sides to fill the gap. If blocks of the same color become adjacent due to this, they merge into a new single region. Jimmy wants to find the best strategy to achieve the highest score. Can you help him?

Input Format

The first line contains an integer $m$ ($1 \le m \le 50$), the number of regions of the same color.
The second line contains $m$ integers, the color of each region (integers between 1 and $m$).
The third line contains $m$ integers, the number of blocks in each region (integers between 1 and 20).

Output Format

Output a single integer: the highest possible score.

4
1 2 3 1
1 3 4 1

29

Hint

Translated by ChatGPT 5