問題文

なむか君は友達のなぷか君と協力して問題 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

入力例 1

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

出力例 1

10

なむか君が問題 1 , 問題 2 を順に解き、なぷか君が問題 3 を解くとき、解く時間の総和は以下のように計算できます。

• なむか君が問題 1 を解く。なむか君の現在の疲れは 0 なので、解くのに A_1+C_0=1+1=2 分かかる。なむか君の疲れが 1 増える。
• なむか君が問題 2 を解く。なむか君の現在の疲れは 1 なので、解くのに A_2+C_1=3+2=5 分かかる。なむか君の疲れが 1 増える。
• なぷか君が問題 3 を解く。なぷか君の現在の疲れは 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