Disjoint-Sparse-Table Optimization

You are given an integer sequence $A$ of length $2Q-1$ and $Q$ intervals $[L_i, R_i)$. Here, $L_i$, $R_i$ satisfy $L_i < R_i$, and each integer between $1$ and $2Q$ appears once as an end of an interval.

Your goal is to create a set $S$ of intervals to satisfy at least one of the following conditions for all $i = 1, 2, \dots, Q$.

• $[L_i, R_i) \in S$
• There exists an integer $x$ ($L_i < x < R_i$) such that $[L_i, x) \in S$ and $[x, R_i) \in S$.

The cost of the set $S$ is defined as follows.

The sum of $A_l + A_{l+1} + \dots + A_{r-1}$ for all intervals $[l,r)$ included in $S$.

Find the minimum cost of the set that satisfies the condition.

$Q$

$L_1$ $R_1$

$\vdots$

$L_Q$ $R_Q$

$A_1$ $A_2$ $\dots$ $A_{2Q-1}$

Output the minimum cost of the set that satisfies the condition. Add a new line at the end of the output.

• All inputs consist of integers.
• $1 \le Q \le 100$
• $1 \le L_i < R_i \le 2Q$
• Each integer from $1$ to $2Q$ appears in $L_1, \dots, L_Q, R_1, \dots, R_Q$.
• $1 \le A_i \le 10^9$

In Sample Input 1, the optimal set is $S = \{[1, 4), [2, 3), [3, 5), [5, 6)\}$, where the cost is $y + 2+7+5=20$.