← 返回题目列表

AtCoder · ajo2025_final_e

E. 大板

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

配点 : 1500 点

問題文

2N \times N 有一个棋盘。 从上到下 i 第几行,从左到右 j 第几列的格子称为格子 (i,j) 。

现在在每个格子中填写非负整数。 但必须满足以下所有条件。

  • i 行目 (1 \leq i \leq 2N) 格子中写入的数值之和 A_i 不超过。
  • j 列目 (1 \leq j \leq N) 格子中写入的数值之和 B_j 不超过。
  • 马斯 (i,j) (1 \leq i \leq N,\ 1 \leq j \leq N) 中写入的数值是 X_i 不超过。
  • 马斯 (i,j) (N+1 \leq i \leq 2N,\ 1 \leq j \leq N) 中写入的数值是 Y_j 不超过。

请求出作为马su上书写的值的总和可能的最大值。

制約

  • 1 \leq N \leq 250000
  • 1 \leq A_i,B_i,X_i,Y_i \leq 10^9
  • 输入全部为整数

入力

输入将以以下格式从标准输入提供。

N
A_1 A_2 \ldots A_{2N}
B_1 B_2 \ldots B_{N}
X_1 X_2 \ldots X_{N}
Y_1 Y_2 \ldots Y_{N}

出力

输出答案。


入力例 1

2
1 8 2 3
6 7
2 3
2 1

出力例 1

12

可以按如下方式书写值。

0 1
3 3
1 1
2 1

入力例 2

3
8 3 8 10 1 5
6 1 11
2 2 3
1 3 3

出力例 2

18

入力例 3

5
43 25 21 38 13 12 17 46 9 13
20 72 97 77 9
5 3 8 6 10
5 4 6 3 1

出力例 3

165

入力例 4

12
253 349 46 454 16 77 491 311 150 181 241 149 143 463 315 378 357 362 35 244 45 380 212 299
87 273 624 223 226 435 988 211 854 285 837 367
40 37 21 1 16 31 22 18 2 39 5 42
29 21 31 25 23 20 35 37 21 41 38 6

出力例 4

4106