← 返回题目列表

AtCoder · npcapc_2024_c

C. 与朋友一起解决

中文机器翻译题面 查看原题

配点 : 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