問題文

2N+2 個の座席が横一列に並んでいる．左から i 番目の座席 (1 \leqq i \leqq 2N+2) の座り心地は A_i である．

2 人組で訪れたグループ客が N 組と，単身で訪れた VIP 客 2 人がおり，これら 2N+2 人の客に 1 人 1 個の座席を割り当てる． ただし，2 人以上の客に同じ座席を割り当ててはいけない．

いま，同じグループに属する 2 人には隣り合う座席を割り当てる必要がある． このとき，VIP 客 2 人に割り当てる 2 個の座席の座り心地の合計をなるべく大きくしたい．

座席の情報が与えられたとき，VIP 客 2 人に割り当てる 2 個の座席の座り心地の合計の最大値を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 200\,000．
• 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq 2N+2)．
• 入力される値はすべて整数である．

小課題

1. (10 点) N = 1．
2. (10 点) N \leqq 2．
3. (10 点) N \leqq 3．
4. (30 点) N \leqq 2\,000．
5. (40 点) 追加の制約はない．

入力例 1

2
20 60 40 30 10 50

出力例 1

90

以下のように割り当てることで，VIP 客 2 人の座席の座り心地の合計は 90 になる．

• 1 組目のグループには左から 1, 2 番目の座席を割り当てる．
• 2 組目のグループには左から 4, 5 番目の座席を割り当てる．
• VIP 客 2 人には左から 3, 6 番目の座席を割り当てる．

VIP 客 2 人の座席の座り心地の合計を 90 より大きくすることはできないので，90 を出力する．

この入力例は小課題 2,3,4,5 の制約を満たす．

入力例 2

1
1000000000 1000000000 1 1

出力例 2

2000000000

この入力例はすべての小課題の制約を満たす．

入力例 3

4
4 10 8 6 7 6 7 8 12 3

出力例 3

16

この入力例は小課題 4,5 の制約を満たす．