配点 : 100 点
問題文
Namuka 与他的朋友 Napuka 一起解决问题。 我最终解决了所有 1 , 問題 2 , \dots , 問題 N 可以得到第 N 问题。
一开始我们俩都很累。 0 然而,问题 1 解决问题时,解决问题的人会变得疲倦。 1 将会增加。问题 i 累了 如果你在 j 时解决了这个问题,那木香君就会 A_i+C_j 需要一分钟,纳普卡君。 需要 B_i+D_j 分钟。然而,2 人们无法同时解决不同的问题。
纳姆卡和纳普卡 求解决 N 问题的最短总时间。
制約
- 1 \leq N\leq 2\times 10^5
- 1 \leq A_i,B_i,C_i,D_i \leq 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
那木香君就是问题所在 按顺序解决 1 , 問題 2 ,纳普卡君就解决了问题。 求解 3 时,总求解时间可计算如下。 解决
- 那木香君就是问题所在 按顺序解决 1 。 Namuka,你现在有多累? 0 所以,要解决 需要 A_1+C_0=1+1=2 分钟。纳姆卡君的疲倦 1 增加。
- 那木香君就是问题所在 按顺序解决 2 。 Namuka,你现在有多累? 1 所以,要解决 需要 A_2+C_1=3+2=5 分钟。纳姆卡君的疲倦 1 增加。
- 纳普卡是问题所在 解决 3 。 Napuka目前的疲劳程度是 需要 0 所以,要解决 需要 B_3+D_0=2+1=3 分钟。纳普卡累了 1 增加。
因此,总和是 2+5+3=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