Namuka 和 Napuka 决定解决全部 $N$ 个问题，即问题 1，问题 2，...，问题 $N$。

最初，他们的疲劳度均为 0，但每解决一个问题，解决该问题的人的疲劳度就会增加 1。当解决问题 $i$ 时，若当前疲劳度为 $j$，Namuka-kun 需要 $A_i + C_j$ 分钟，Napuka-kun 需要 $B_i + D_j$ 分钟。两人不能同时解决问题。

求 Namuka 和 Napuka 解决全部 $N$ 个问题所需的最少总时间。

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i, B_i, C_i, D_i \le 10^9$

输入格式

输入通过标准输入按以下格式给出：

$N$ $A_1 \ A_2 \ \dots \ A_N$ $B_1 \ B_2 \ \dots \ B_N$ $C_0 \ C_1 \ \dots \ C_{N-1}$ $D_0 \ D_1 \ \dots \ D_{N-1}$

输出格式

输出答案。

样例

样例输入 1

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

样例输出 1

10

样例输入 2

5
2 4 3 1 2
9 2 5 3 8
1 2 8 3 2
5 4 3 2 1

样例输出 2

28

样例输入 3

8
21 85 72 22 81 20 88 28
75 22 78 92 55 56 73 44
39 14 64 27 73 42 16 84
27 7 91 85 69 95 70 27

样例输出 3

621

说明

对于第一个样例：

当 Namuka 按顺序解决问题 1 和问题 2，而 Napuka 解决问题 3 时，总时间计算如下：

• Namuka 解决问题 1。Namuka 当前疲劳度为 0，因此耗时 $A_1 + C_0 = 1 + 1 = 2$ 分钟。Namuka 的疲劳度增加 1。
• Namuka 解决问题 2。Namuka 当前疲劳度为 1，因此耗时 $A_2 + C_1 = 3 + 2 = 5$ 分钟。Namuka 的疲劳度增加 1。
• Napuka 解决问题 3。Napuka 当前疲劳度为 0，因此耗时 $B_2 + D_0 = 2 + 1 = 3$ 分钟。Napuka 的疲劳度增加 1。

因此，总时间为 $2 + 5 + 3 = 10$ 分钟，这是最小值。