問題文

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 以下である．

マスに書かれた値の総和としてありうる最大値を求めてください．

制約

• 1 \leq N \leq 250000
• 1 \leq A_i,B_i,X_i,Y_i \leq 10^9
• 入力はすべて整数

入力例 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