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 翻译