说明

给定一个长度为 $2Q - 1$ 的整数序列 $A$，以及 $Q$ 个区间 $[L_i, R_i)$。其中，$L_i, R_i$ 满足 $L_i < R_i$，并且 $1$ 到 $2Q$ 之间的每个整数都恰好作为某个区间的端点出现一次。

你的目标是创建一个区间集合 $S$，使得对于所有 $i = 1, 2, \ldots, Q$，至少满足以下条件之一：

• $[L_i, R_i) \in S$
• 存在一个整数 $x$（$L_i < x < R_i$），使得 $[L_i, x) \in S$ 且 $[x, R_i) \in S$。

集合 $S$ 的代价定义如下：

• 对于 $S$ 中包含的所有区间 $[l, r)$，计算 $A_l + A_{l+1} + \ldots + A_{r-1}$ 的总和。

求满足条件的最小代价。

输入格式

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

输入满足以下约束：

• 所有输入均为整数。
• $1 \leq Q \leq 100$
• $1 \leq L_i < R_i \leq 2Q$
• $1$ 到 $2Q$ 之间的每个整数都出现在 $L_1, \ldots, L_Q, R_1, \ldots, R_Q$ 中。
• $1 \leq A_i \leq 10^9$

输出格式

输出满足条件的最小代价。

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

提示

在样例输入 1 中，最优集合为 $S = \{[1, 4), [2, 3), [3, 5), [5, 6)\}$，其代价为 $6 + 2 + 7 + 5 = 20$。

翻译由 DeepSeek V3.2 完成