AT_utpc2025_j Jelly

$ 1, 2, \dots, N $ の番号がつけられた $ N $ 種類の食べ物と水ゼリーの、合計 $ N+1 $ 種類の食べ物があります。 $ i = 1, 2, \dots, N $ について、食べ物 $ i $ の甘さは $ A_i $ で、辛さは $ B_i $ です。また、水ゼリーの甘さは $ 0 $ で、辛さは $ 0 $ です。 UTPC 君は、はじめに水ゼリーを食べ、続いて食べ物 $ 1, 2, \dots, N $ を任意の順番で $ 1 $ 回ずつ食べ、最後に水ゼリーを食べます。 UTPC 君がはじめに水ゼリーを食べ終わった時点での幸福度は $ 0 $ です。これ以降、食べ物を食べる度に、UTPC 君の幸福度は次のように変化します。 - 食べる食べ物の甘さを $ a $ 、辛さを $ b $ とし、その直前に食べた食べ物の甘さを $ a' $ 、辛さを $ b' $ とする。このとき、UTPC 君の幸福度は $ \max(a - a', b - b') $ だけ増加する。幸福度の増加量は負であることもある。 食べ物 $ 1, 2, \dots, N $ を食べる順番を工夫したときの、UTPC 君の最終的な幸福度の最大値を求めてください。

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

答えを $ 1 $ 行に出力せよ。

### Sample Explanation 1 食べ物 $ 1,2,3,4 $ の順番で食べればよいです。このとき、はじめに水ゼリーを食べ終わった以降の UTPC 君の幸福度の変化は以下の通りです。 - 食べ物 $ 1 $ を食べる。UTPC 君の幸福度は $ \max(1-0,4-0) = 4 $ だけ増加し、 $ 4 $ となる。 - 食べ物 $ 2 $ を食べる。UTPC 君の幸福度は $ \max(3-1,1-4) = 2 $ だけ増加し、 $ 6 $ となる。 - 食べ物 $ 3 $ を食べる。UTPC 君の幸福度は $ \max(2-3,3-1) = 2 $ だけ増加し、 $ 8 $ となる。 - 食べ物 $ 4 $ を食べる。UTPC 君の幸福度は $ \max(3-2,4-3) = 1 $ だけ増加し、 $ 9 $ となる。 - 水ゼリーを食べる。UTPC 君の幸福度は $ \max(0-3,0-4) = -3 $ だけ増加し、 $ 6 $ となる。 ### Constraints - 入力は全て整数 - $ 1 \leq N \leq 5 \times 10^5 $ - $ 0 \leq A_i,B_i \leq 10^9 $