AT_abc352_c [ABC352C] Standing On The Shoulders

[problemUrl]: https://atcoder.jp/contests/abc352/tasks/abc352_c $ N $ 人の巨人がいます。巨人にはそれぞれ $ 1,\ 2,\ \ldots,\ N $ の名前がついており、巨人 $ i $ が地面に立ったとき、肩の高さは $ A_i $、頭の高さは $ B_i $ となります。 あなたは $ (1,\ 2,\ \ldots,\ N) $ を並べ替えて得られる数列 $ (P_1,\ P_2,\ \ldots,\ P_N) $ を選び、以下の規則に従って $ N $ 人の巨人を積み上げることができます。 - まず地面に巨人 $ P_1 $ を立たせる。巨人 $ P_1 $ の肩は地面を基準として $ A_{P_1} $、頭は地面を基準として $ B_{P_1} $ の高さとなる。 - $ i\ =\ 1,\ 2,\ \ldots,\ N\ -\ 1 $ の順に巨人 $ P_i $ の肩の上に巨人 $ P_{i\ +\ 1} $ を立たせる。巨人 $ P_i $ の肩が地面を基準として高さ $ t $ のとき、巨人 $ P_{i\ +\ 1} $ の肩は地面を基準として $ t\ +\ A_{P_{i\ +\ 1}} $、頭は地面を基準として $ t\ +\ B_{P_{i\ +\ 1}} $ の高さとなる。 一番上に立っている巨人、すなわち巨人 $ P_N $ の地面を基準とした頭の高さとして実現できる最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

答えを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ B_i\ \leq\ 10^9 $ - 入力される値はすべて整数 ### Sample Explanation 1 $ (P_1,\ P_2,\ P_3)\ =\ (2,\ 1,\ 3) $ とすると、地面を基準として巨人 $ 2 $ は肩の高さが $ 5 $、頭の高さが $ 8 $、巨人 $ 1 $ は肩の高さが $ 9 $、頭の高さが $ 15 $、巨人 $ 3 $ は肩の高さが $ 11 $、頭の高さが $ 18 $ となります。 一番上に立っている巨人の頭の高さが地面を基準として $ 18 $ より大きくなることはないため $ 18 $ を出力します。