Block Elimination Game

Jimmy is fascinated by a game called the Block Elimination Game. In this game, a row of colored blocks is arranged and contiguous blocks of the same color form a region. The game uses a simplified input format where consecutive blocks of the same color are compressed into a region represented by a number indicating its color and a number indicating the count of blocks in that region.

When you remove a region containing x blocks, you earn \(x^2\) points. After a removal, the remaining blocks shift: they fall vertically to fill empty spaces and, if an entire column is cleared, the blocks to the right will shift left. This means that after each removal, regions that become adjacent and share the same color will merge, which can lead to a higher score when removed later.

Your task is to determine the maximum score that can be obtained by removing all the blocks in an optimal order.

The input is provided in compressed format as follows:

• The first line contains an integer k—the number of regions.
• The second line contains k space‐separated integers representing the color of each region.
• The third line contains k space‐separated integers representing the count of blocks in each corresponding region.

For example, the input:

4
1 2 3 1
1 3 4 1

represents a block sequence which decompresses to: [1] [2,2,2] [3,3,3,3] [1]. The optimal removal order for this case gives a maximum score of 29 points.

inputFormat

Input Format:

• The first line contains an integer k, the number of regions.
• The second line contains k space-separated integers representing the color of each region.
• The third line contains k space-separated integers representing the count of blocks in each corresponding region.

outputFormat

Output Format:

• Output a single integer, which is the maximum score that can be obtained by optimally removing all the blocks.

sample

4
1 2 3 1
1 3 4 1

29