問題文

1, 2, \ldots, N の番号が付いた N 人の人が，この順で一列に並んでいる．

これから，隣り合う 2 人の組のうちいくつかを，ペアとして組み合わせる．ここで，どのペアにも属さない人がいても良いが，複数のペアに属する人がいてはならない．

人 i (1 \leqq i \leqq N) は，ペアに属しているとき A_i，属していないとき B_i の嬉しさを得る．

それぞれの人の得る嬉しさの合計としてあり得る最大値を出力せよ．

制約

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

小課題

1. (5 点) N=2．
2. (5 点) N=3．
3. (15 点) N \leqq 20．
4. (15 点) A_i \leqq B_i (1 \leqq i \leqq N)．
5. (20 点) A_i \geqq B_i (1 \leqq i \leqq N)，N \leqq 2\,000．
6. (15 点) A_i \geqq B_i (1 \leqq i \leqq N)．
7. (25 点) 追加の制約はない．

入力例 1

2
1 5
2 3

出力例 1

8

ペアの組み合わせ方は，次の 2 通りである．

• ペアを作らない．嬉しさの合計は 5+3=8 である．
• 人 1 と人 2 をペアとして組み合わせる．嬉しさの合計は 1+2=3 である．

嬉しさの合計としてあり得る最大値は 8 である．したがって 8 を出力する．

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

入力例 2

3
3 1
4 1
5 9

出力例 2

16

ペアの組み合わせ方は，次の 3 通りである．

• ペアを作らない．嬉しさの合計は 1+1+9=11 である．
• 人 1 と人 2 をペアとして組み合わせる．嬉しさの合計は 3+4+9=16 である．
• 人 2 と人 3 をペアとして組み合わせる．嬉しさの合計は 1+4+5=10 である．

嬉しさの合計としてあり得る最大値は 16 である．したがって 16 を出力する．

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

入力例 3

9
7 5
9 2
8 4
3 2
8 0
9 6
5 4
7 4
5 3

出力例 3

60

嬉しさの合計としてあり得る最大値は 60 である．したがって 60 を出力する．

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

入力例 4

20
561489116 275685026
758578808 69451200
667191502 185442303
202651868 608800580
288797924 407149971
923620429 184024159
308892271 910130037
86744998 917256749
215642564 754302313
5047571 841289455
800504440 85841800
186284228 276350136
718997126 928102355
897137549 43854605
963672884 35595326
40481197 750494585
139302189 184491652
116025250 719563820
334978342 266547935
728598966 631310980

出力例 4

13439481644

出力が 32bit 整数型に収まらない場合があることに注意せよ．

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