Company A is selling a popular computer product. As the CEO of Company A, Little A plans to develop a specific production and sales plan for the next $N$ consecutive sales quarters. It is known that the order quantity for the product in the $i$-th quarter is $D_i$. In the $i$-th quarter, Company A can satisfy user orders in the following ways:

• Produce new products in the $i$-th quarter to sell.
• If there is excess inventory from before the $i$-th quarter, it can be sold directly in the $i$-th quarter (note that there is no inventory before the first quarter).
• Company A may choose not to fulfill all orders in the $i$-th quarter, deferring the unfulfilled orders to the next quarter ($i+1$).

Company A needs to consider the following costs: the cost of producing new products, the additional storage cost for inventory, and the compensation cost for deferring orders. Due to labor and resource limitations, the number of new products that can be produced in each quarter is limited, and the costs and production limits vary by quarter, as follows:

• In the $i$-th quarter, at most $U_i$ new products can be produced, with a cost of $P_i$ per unit.
• Products saved from the $i$-th quarter can be used for sales in future quarters. For each product, if it is stored from the $i$-th quarter to the $(i+1)$-th quarter, an additional storage fee of $M_i$ must be paid (note that products saved to the next quarter may be stored again).
• For each unit of order deferred from the $i$-th quarter to the next, Company A must pay a compensation fee of $C_i$ to the user (note that if an order is deferred to the next quarter, it may be deferred again, and the cost is calculated based on the deferral fee of the subsequent quarter).

After the $N$-th quarter, Company A must fulfill all previous user orders. It is guaranteed that the total number of products Company A can produce is not less than the total order quantity, meaning there must exist a production and sales plan that satisfies all user orders. Little A wants to know how to arrange the production and sales of the products to minimize the total cost while satisfying all orders.

Input

The first line contains a positive integer $N$, representing the number of sales quarters. The second line contains $N$ non-negative integers $D_1, D_2, \dots, D_N$, representing the order quantity in the $i$-th quarter. The third line contains $N$ non-negative integers $U_1, U_2, \dots, U_N$, representing the maximum number of new products that can be produced in the $i$-th quarter. The fourth line contains $N$ non-negative integers $P_1, P_2, \dots, P_N$, representing the cost of producing one new product in the $i$-th quarter. The fifth line contains $N-1$ non-negative integers $M_1, M_2, \dots, M_{N-1}$, representing the additional cost required to store one product from the $i$-th quarter to the $(i+1)$-th quarter. The sixth line contains $N-1$ non-negative integers $C_1, C_2, \dots, C_{N-1}$, representing the compensation fee for each unit of order that is not completed in the $i$-th quarter and is deferred to the $(i+1)$-th quarter.

Output

The output contains only one non-negative integer, representing the minimum total cost for the company.

Examples

Input 1

4
3 2 1 2
2 5 2 2
5 1 5 5
1 2 1
5 3 3

Output 1

30

Note

In the first quarter, 2 products are produced; in the second quarter, 5 products are produced; in the third quarter, no products are produced; in the fourth quarter, 1 product is produced. The production cost is $2 \times 5 + 5 \times 1 + 0 \times 5 + 1 \times 5 = 20$.

Since at most 2 products can be produced in the first quarter, the order of 3 units cannot be fully satisfied, so 1 unit of the order is deferred to the second quarter, with a compensation fee of 5.

In the second quarter, because 1 unit of the order was deferred from the first quarter, the order quantity becomes 3. This quarter produced 5 products, and the remaining 2 are stored. The third quarter sells the inventory directly, and the 1 extra product is stored until the fourth quarter. Adding the 1 product produced in the fourth quarter, all orders are satisfied. The total storage cost is $2 \times 2 + 1 \times 1 = 5$.

The total cost is $20 + 5 + 5 = 30$.

Constraints

For 30% of the data, $N \le 1,000$. For 100% of the data, $1 \le N \le 100,000$, $1 \le D_i, U_i, P_i, M_i, C_i \le 10,000$.