Question

Minimum Cost to Schedule Placement Drives

The placement cell is scheduling N placement drives in a fixed sequence. Drive i has a load value load[i] and a coordination cost coord[i].

You must partition the N drives, in order, into one or more contiguous batches (groups of consecutive drives run together). If a batch is the k-th batch overall (1-indexed, in the order batches occur) and spans drives l through r inclusive, its cost is:

(load[0] + load[1] + ... + load[r] + rate * k) * (coord[l] + coord[l + 1] + ... + coord[r])

Note that the load sum always starts from index 0 of the entire array, regardless of where the batch itself starts, while the coordination sum is only over the batch's own range.

Return the minimum possible total cost across all batches, over every valid way to partition the N drives into contiguous batches.

Input

The first line contains a single integer KaTeX can only parse string typed expression — the number of placement drives.

The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression.

The third line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression.

The fourth line contains a single integer KaTeX can only parse string typed expression.

Output

Print a single integer — the minimum total cost across all batches.

Example

Example 1:
Input

Output

Explanation
The best partition is batches KaTeX can only parse string typed expression and KaTeX can only parse string typed expression. First batch (KaTeX can only parse string typed expression, drives KaTeX can only parse string typed expression): KaTeX can only parse string typed expression. Second batch (KaTeX can only parse string typed expression, drive KaTeX can only parse string typed expression): KaTeX can only parse string typed expression. Total KaTeX can only parse string typed expression.

Example 2:
Input

9

4 8 5 1 14 2 2 12 1

7 2 8 4 2 2 1 1 2

7

Output

Explanation
The best partition is batches KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression. First batch (KaTeX can only parse string typed expression): KaTeX can only parse string typed expression. Second batch (KaTeX can only parse string typed expression): KaTeX can only parse string typed expression. Third batch (KaTeX can only parse string typed expression): KaTeX can only parse string typed expression. Total KaTeX can only parse string typed expression.

Online

Explore Newton School

Recent Questions

Most Solved Questions

Least Solved Questions