考虑一个长度为 $2k-1$ 的整数序列 $c$。同时考虑 $k$ 个区间 $[\ell_i, r_i)$。其中，$\ell_i$ 和 $r_i$ 满足 $\ell_i < r_i$，且 $1$ 到 $2k$ 之间的每个整数在这些区间端点中恰好出现一次。

给定该序列，创建一个区间集合 $s$。集合中的每个区间 $[\ell, r)$ 必须满足 $1 \le \ell < r \le 2k$。此外，对于所有 $i = 1, 2, \dots, k$，集合 $s$ 必须满足以下两个条件中的至少一个：

• $[\ell_i, r_i) \in s$，
• 存在一个整数 $x$ ($\ell_i < x < r_i$)，使得 $[\ell_i, x) \in s$ 且 $[x, r_i) \in s$。

集合 $s$ 的代价定义为所有包含在 $s$ 中的区间 $[\ell, r)$ 的 $c_\ell + c_{\ell+1} + \dots + c_{r-1}$ 之和。

求满足所有条件的集合的最小代价。

输入格式

第一行包含一个整数 $k$：区间的数量 ($1 \le k \le 100$)。

接下来的 $k$ 行，第 $i$ 行包含两个整数 $\ell_i$ 和 $r_i$：第 $i$ 个区间的左端点（包含）和右端点（不包含）($1 \le \ell_i < r_i \le 2k$，且 $1$ 到 $2k$ 之间的每个整数在这些行中恰好出现一次)。

最后一行包含 $2k-1$ 个整数：序列 $c_i$ ($1 \le c_i \le 10^9$)。

输出格式

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

样例

样例输入 1

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

样例输出 1

27

样例输入 2

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

样例输出 2

82