国际管道与电缆公司在太平洋铺设了一条互联网电缆。然而，它停止工作了！不过别担心，这并不意外，因为这种情况有时是由鲨鱼袭击引起的。该电缆由 $N+1$ 个段组成，每两个相邻段之间都有一个中继器。中继器按其在电缆中的位置从左到右用 $1$ 到 $N$ 的不同整数标识。

信号沿电缆从左向右传输。如果信号没有到达某个中继器，则称该中继器为离线（offline）；这表明在该中继器之前存在故障段。相反，如果中继器接收到数据，则称其为在线（online）；这表明在该中继器之后存在故障段。技术人员已确定存在唯一的故障段。为了定位并修复它，需要进行一次远征。

远征从 $1$ 号中继器开始，并重复以下三个步骤，直到定位到故障段：航行到某个中继器，潜水到该中继器，并诊断信号是否到达该中继器。如果信号到达了某段的第一个端点但没有到达第二个端点，则定位到该故障段。一旦识别出故障段，它就会被修复。

远征计划定义了根据沿途所做的诊断，行程将如何进行。上图显示了 $N=3$ 个中继器（即 $N+1=4$ 个段）的一种可能场景。针对这种情况的五种可能的远征计划如下：

1. 诊断 $2$ 号中继器。如果它离线，则诊断 $1$ 号中继器以决定前两个段中的哪一个是故障段。相反，如果 $2$ 号中继器在线，则诊断 $3$ 号中继器以决定最后两个段中的哪一个是故障段。
2. 按 $1, 2, 3$ 号中继器的顺序进行诊断，在找到故障段时提前停止。
3. 按 $1, 3, 2$ 号中继器的顺序进行诊断，在找到故障段时提前停止。
4. 按 $3, 1, 2$ 号中继器的顺序进行诊断，在找到故障段时提前停止。
5. 按 $3, 2, 1$ 号中继器的顺序进行诊断，在找到故障段时提前停止。

远征的总成本由航行成本、潜水成本和修复成本组成。航行成本与航行距离成正比。每次潜水的潜水成本与中继器的深度成正比。故障段的修复成本取决于其铺设的地形。在我们的示例中，第一个提到的远征计划的成本如下：

• 如果第一段发生故障，远征队航行到 $2$ 号中继器，潜水，航行回 $1$ 号中继器，潜水，并修复该段。因此，航行成本为 $1 + 1 = 2$，潜水成本为 $8 + 3 = 11$，修复成本为 $7$，总计 $2 + 11 + 7 = 20$。
• 如果第二段发生故障，总成本为 $(1 + 1) + (8 + 3) + (1) = 14$。
• 如果第三段发生故障，总成本为 $(1 + 1) + (8 + 2) + (2) = 14$。
• 如果第四段发生故障，总成本为 $(1 + 1) + (8 + 2) + (12) = 24$。

由于网络中断与墨菲定律之间的高度相关性，远征计划最准确的成本估算为其可能达到的最大值。也就是说，我们应该认为故障段总是那个使远征成本达到最大的段。因此，第一个远征计划的估算成本为 $24$。你的任务是找到所有远征计划中的最小估算成本。在我们的示例中，按 $1, 3, 2$ 号中继器顺序进行诊断的远征计划，根据故障段的不同，总成本分别为 $10, 17, 18$ 或 $19$。这意味着其估算成本为 $19$，这是所有远征计划中的最小值。

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 3000$)，表示中继器的数量。 第二行包含 $N-1$ 个整数 $S_1, S_2, \dots, S_{N-1}$ ($0 \le S_i \le 10^9$ 对于 $i = 1, 2, \dots, N-1$)，其中 $S_i$ 是在 $i$ 号和 $i+1$ 号中继器之间航行的成本。 第三行包含 $N$ 个整数 $D_1, D_2, \dots, D_N$ ($0 \le D_i \le 10^9$ 对于 $i = 1, 2, \dots, N$)，其中 $D_i$ 是潜水到 $i$ 号中继器的成本。 最后一行包含 $N+1$ 个整数 $F_1, F_2, \dots, F_{N+1}$ ($0 \le F_i \le 10^9$ 对于 $i = 1, 2, \dots, N+1$)，其中 $F_i$ 是修复第 $i$ 个段的成本。

输出格式

输出一行，包含一个整数，表示所有远征计划中的最小估算成本。

样例

样例输入 1

3
1 1
3 8 2
7 1 2 12

样例输出 1

19

样例输入 2

2
2
5 1
1 2 6

样例输出 2

12