题目描述

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, \ldots, 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} + \ldots + A_{r-1}$ for all intervals $[l, r)$ included in $S$.

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

输入格式

$$\begin{aligned} &Q \\ &L_1 \ R_1 \\ &\vdots \\ &L_Q \ R_Q \\ &A_1 \ A_2 \ \ldots \ A_{2Q-1} \end{aligned} $$

The input satisfies the following constraints.

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

输出格式

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

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

20

5
3 7
1 10
5 9
4 8
2 6
6 4 8 5 9 8 9 8 2

132

提示

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