安妮已经厌倦了赢得每场编码比赛和耕作无限评级。今天,她要去种土豆。
安妮的花园是一个无限的二维平面。她有 $$$n$$$ 个土豆要种植,第 $$$i$$$ 个土豆必须种植在 $$$(x_i,y_i)$$$。从点 $$$(0, 0)$$$ 开始,安妮开始行走,一步中她可以向右或向上移动一个单位(将 $$$x$$$ 或 $$$y$$$ 坐标分别增加 $$$1$$$)。在行走过程中的任何时刻 $$$(X,Y)$$$,她都可以使用土豆枪在任意点种植一些土豆,消耗 $$$\max(|X-x|,|Y-y|)$$$ 单位的能量,以便在 $$$(x,y)$$$ 处种植土豆。求种植每个马铃薯所需的最低总能量。
请注意,安妮可以从任意地点种植任意数量的土豆。
输入
第一行包含整数 $$$n$$$ ($$$1 \le n \le 800\,000$$$)。
接下来的 $$$n$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$0 \le x_i,y_i \le 10^9$$$),代表第 $$$i$$$ 个马铃薯的位置。可能应该在同一地点种植一些土豆。
输出
打印种植所有土豆的最低总能量。
示例
输入 #1
2 1 1 2 2
输出 #1
0
输入 #2
2 1 1 2 0
输出 #2
1
输入 #3
3 5 5 7 7 4 9
输出 #3
2
输入#4
10 5 1 4 0 9 6 0 2 10 1 9 10 3 10 0 10 8 9 1 5
输出#4
19
输入 #5
10 1 1 2 2 2 0 4 2 4 0 2 0 0 2 4 0 4 2 5 1
输出 #5
6
注意
在$$$1$$$示例中,安妮可以直接前往每个地点并种植土豆,无需任何能量。
在示例 $$$2$$$ 中,移动到 $$$(1,0)$$$,安妮使用 $$$1$$$ 能量种植第二个土豆。接下来,她前往 $$$(1,1)$$$ 并用 $$$0$$$ 能量种植第一个土豆。