A93899.Alice的石子合并

有一排从左到右的 $n$ 堆石子，初始依次编号为 $1,2,\dots,n$。
每个原始第 $i$ 堆自带一对属性 $(a_i, b_i)$（非负整数）。

你可以反复对相邻两堆进行合并，直到只剩下一堆。一次合并必须选择一对当前相邻的块 $X$（在左）与 $Y$（在右），并指定哪一方是主动方：

• 右并左（右块主动）：将右块 $Y$ 并入左块 $X$。
  本次费用为 $a_Y$（主动方当前携带的 $a$）。合并后，新块的属性完全继承被动方 $X$ 的属性。
• 左并右（左块主动）：将左块 $X$ 并入右块 $Y$。
  本次费用为 $b_X$（主动方当前携带的 $b$）。合并后，新块的属性完全继承被动方 $Y$ 的属性。

请计算，将所有石子最终合并成一堆的最小总代价。

• 第一行一个整数 $n$。
• 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。
• 第三行 $n$ 个整数 $b_1,b_2,\dots,b_n$。

输出一个整数，为最小总代价。

数据范围

测试点	$n$ 范围	$a_i,b_i$ 范围
$1\sim 2$	$2\le n<20$	$0\le a_i,b_i\le 10^{12}$
$3\sim 6$	$20\le n<500$	$0\le a_i,b_i\le 10^{12}$
$7\sim 20$	$500\le n\le 2\times 10^{5}$	$0\le a_i,b_i\le 10^{12}$

样例解释

合并过程

第 1 次：右并左

• 操作：主动 $2$ 并到 被动 $1$
• 费用：$a_2=2$
• 继承：保留锚点 $1$ 的属性
• 新状态：
  [1..2]@1(a=5,b=9) | [3..3]@3(a=6,b=8) | [4..4]@4(a=3,b=1) | [5..5]@5(a=4,b=2)

---

第 2 次：右并左

• 操作：主动 $3$ 并到 被动 $1$
• 费用：$a_3=6$
• 继承：保留锚点 $1$ 的属性
• 新状态：
  [1..3]@1(a=5,b=9) | [4..4]@4(a=3,b=1) | [5..5]@5(a=4,b=2)

---

第 3 次：左并右

• 操作：主动 $4$ 并到 被动 $5$
• 费用：$b_4=1$
• 继承：保留锚点 $5$ 的属性
• 新状态：
  [1..3]@1(a=5,b=9) | [4..5]@5(a=4,b=2)

---

第 4 次：右并左

• 操作：主动 $5$ 并到 被动 $1$
• 费用：$a_5=4$
• 继承：保留锚点 $1$ 的属性
• 新状态：
  [1..5]@1(a=5,b=9)（完成）