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$ 号食物按照任意顺序各吃一次，最后再吃一次水ゼリー。

UTPC 君刚吃完第一次水ゼリー时，幸福度为 $0$。之后每吃一种食物，幸福度按照如下方式变化：

• 设当前食物的甜度为 $a$，辣度为 $b$，上一个食物的甜度为 $a'$，辣度为 $b'$，则幸福度会增加 $\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

按序吃 $1,2,3,4$ 号食物即可。此时，从吃完第一次水ゼリー之后，UTPC 君的幸福度变化如下：

• 吃 $1$ 号食物：幸福度增加 $\max(1-0,4-0)=4$，变为 $4$。
• 吃 $2$ 号食物：幸福度增加 $\max(3-1,1-4)=2$，变为 $6$。
• 吃 $3$ 号食物：幸福度增加 $\max(2-3,3-1)=2$，变为 $8$。
• 吃 $4$ 号食物：幸福度增加 $\max(3-2,4-3)=1$，变为 $9$。
• 吃水ゼリー：幸福度增加 $\max(0-3,0-4)=-3$，变为 $6$。

数据范围

• 输入均为整数。
• $1 \leq N \leq 5 \times 10^5$
• $0 \leq A_i,B_i \leq 10^9$

由 ChatGPT 5 翻译