← 返回题目列表

AtCoder · utpc2025_j

J. 果冻

中文机器翻译题面 查看原题

配点 : 100 点

問題文

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 最终幸福水平的最大值。 你应该按照

制約

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

入力

输入是按以下格式从标准输入给出的。

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答案 1 行输出。 由于字符串以


入力例 1

4
1 4
3 1
2 3
3 4

出力例 1

6

食品 求设计饮食顺序 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 变为。

入力例 2

3
1 2
2 1
1 2

出力例 2

3

入力例 3

6
3 1
4 1
5 9
2 6
5 3
5 8

出力例 3

18