Floor Dust Cleaning

You are given a sequence of n floor panels numbered from 1 to n. Each panel has a type c_i (either 0 or 1) and a dust level a_i. Initially, all panels are dirty. Your task is to clean all the floor panels with a series of operations while minimizing the total energy used.

In each operation, you can select two indices i and j (1 ≤ i ≤ j ≤ n) such that:

• The types of the i-th and j-th panels are the same, i.e. c_i = c_j.
• Both panels i and j have not been cleaned before this operation.

Then you spend an energy equal to a_i + a_j to clean every panel from index i to j (inclusive). Note that choosing the same index for both i and j is allowed; in this case the cost is 2a_i.

The goal is to determine the minimum total energy required to clean all the panels.

Hint: Think of partitioning the sequence into contiguous segments where, for each segment, the first and last panels have the same type, and you pay the sum of their dust levels. Dynamic programming can be used to solve this optimization problem.

inputFormat

The first line contains an integer n (1 ≤ n).

The second line contains n space-separated integers c₁, c₂, ..., c_n, where each c_i is either 0 or 1.

The third line contains n space-separated integers a₁, a₂, ..., a_n representing the dust levels of the panels.

outputFormat

Output a single integer — the minimum total energy required to clean all the floor panels.

sample

1
0
5

10