#arc147c. [arc147_c]Min Diff Sum

[arc147_c]Min Diff Sum

题目描述

NN 个人,编号为 1,2,ldots,N1,2,\\ldots ,N,他们要站在数轴上。我们用 xix_i 表示第 ii 个人所站的坐标。因此,xix_i 应该是一个整数,满足 LileqxileqRiL_i \\leq x_i \\leq R_i。可以有多个人站在同一个坐标上。

我们定义不满意度如下公式:

displaystylesumi=1N1sumj=i+1Nxjxi\\displaystyle\\sum_{i=1}^{N-1}\\sum_{j=i+1}^{N}|x_j-x_i|

求不满意度的最小可能值。

约束条件

  • 2leqNleq3times1052 \\leq N \\leq 3 \\times 10^5
  • 1leqLileqRileq107,(1leqileqN)1 \\leq L_i \\leq R_i \\leq 10^7 \\,(1 \\leq i \\leq N)
  • 输入中的所有值均为整数。

输入

从标准输入读取输入数据,输入格式如下:

NN

L1L_1 R1R_1

L2L_2 R2R_2

vdots\\vdots

LNL_N RNR_N

输出

输出答案。


示例输入1

3
1 3
2 4
5 6

示例输出1

如果我们令 x1=3,x2=4,x3=5x_1=3,x_2=4,x_3=5,那么不满意度为 44。我们无法使其小于或等于 33,因此答案是 44


示例输入2

3
1 1
1 1
1 1

示例输出2


示例输入3

6
1 5
2 4
1 1
4 4
3 6
3 3

示例输出3

15