给定一张 $n$ 个点的完全图，点的编号为 $1 \sim n$，对于两个点 $i, j(i \neq j)$，它们之间的边权为 $a_{i+j}$。请你求解这张图的最小生成树，你只需要给出最小生成树的边权和即可。

Input

第一行一个正整数 $n$ ($2 \leq n \leq 2 \times 10^5$) 表示图的点数。

第二行 $2n-3$ 个正整数，表示 $a_{3} \sim a_{2n-1}$ ($1 \leq a_i \leq 10^9$)。

Output

一行一个正整数表示答案。

Examples

Input

4
7 6 7 6 4

Output

16

Input

8
21 5 28 58 73 32 43 96 72 54 35 28 5

Output

151

Scoring

对于 $20\%$ 的测试点： $n \leq 1000$。

对于 $30\%$ 的测试点： $n \leq 10000$。

对于另外 $20\%$ 的测试点： $a_i$ 在 $[1, 10^9]$ 中均匀随机生成。

对于所有测试点：$1 \leq n \leq 2 \times 10^5，1 \leq a_i \leq 10^9$。