← 返回题目列表

AtCoder · arc147_c

C. 最小差异和

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

分数: 600 点

问题陈述

N 人,已编号 1,2,\ldots ,N,将站在数轴上。 我们用 x_i 人的坐标 i 位于。 然后, x_i 应该是满足以下条件的整数 L_i \leq x_i \leq R_i。 多个人可以占据同一个坐标。

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

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

找到不满意程度的最小可能值。

约束

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

输入

输入由标准输入按以下格式给出:

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

输出

打印答案。


示例输入 1

3
1 3
2 4
5 6

示例输出 1

4

如果我们让 x_1=3,x_2=4,x_3=5,我们得到的不满意程度为 4。我们做不到 3 或更少,所以答案是 4.


示例输入 2

3
1 1
1 1
1 1

示例输出 2

0

示例输入 3

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

示例输出 3

15