G - Tea Party 2
Assam
2
s
1024
MB
300
点
問題文
花子さんはお茶会に参加しました。
このお茶会では、$N$ 回にわたり紅茶とマカロンが運ばれてきます。
$i$ 回目に運ばれてくる紅茶の美味しさは $t_i$、マカロンの美味しさは $s_i$ です。
花子さんは、このうちどちらかを食べることができます。
どちらも食べないことはできますが、両方食べることはできません。
さて、このお茶会には変わったルールがあり、マカロンと紅茶を交互に食べなくてはなりません。
$N$ 回の中で食べた美味しさの合計が最大になるように食べた時、美味しさの値はいくつになりますか？
制約
- $N, t_i, s_i$ は整数
- $1\leq N\leq 2\times 10^5$
- $1\leq t_i, s_i\leq 2\times 10^5$
入力
入力は以下の形式で与えられます。
$N$
$t_1 \quad s_1$
$\vdots$
$t_N \quad s_N$
出力
最大となる美味しさの値を一行で表示してください。
入力例 1
5
1 5
5 1
1 1
1 5
5 1
出力例 1
20
マカロン→紅茶→食べない→マカロン→紅茶のように行動すると美味しさ $20$ が達成でき、これが最大となります。
入力例 2
10
216 239
862 919
350 235
75 983
533 676
328 327
864 366
749 18
543 60
972 56
出力例 2
5224