AT_cf16_exhibition_final_f Intervals

すぬけ君收到了 $N$ 个区间作为生日礼物。第 $i$ 个区间是 $[-L_i, R_i]$。保证 $L_i$ 和 $R_i$ 都是正数。也就是说，原点一定在每个区间的内部。 すぬけ君不喜欢区间重叠，因此他打算移动一些区间。对于任意正整数 $d$，他可以支付 $d$ 美元，将一个区间整体向左或向右移动 $d$ 的距离。也就是说，如果选择的区间是 $[a, b]$，可以将其变为 $[a+d, b+d]$ 或 $[a-d, b-d]$。 すぬけ君可以进行任意次数的这种操作。所有操作结束后，任意两个区间都不能有重叠（区间端点重合是允许的）。更准确地说，任意两个区间的交集长度必须为 $0$。 请计算达成目标所需的最小总花费。

输入通过标准输入给出，格式如下： > $N$ > $L_1\ R_1$ > $L_2\ R_2$ > $\vdots$ > $L_N\ R_N$

输出达成目标所需的最小总花费。

## 限制条件 - $1 \leq N \leq 5000$ - $1 \leq L_i, R_i \leq 10^9$ - 输入的所有数均为整数。 ## 样例解释 1 一种最优方案如下： - 将区间 $[-2, 7]$ 以 $8$ 美元移动到 $[6, 15]$ - 将区间 $[-2, 5]$ 以 $1$ 美元移动到 $[-1, 6]$ - 将区间 $[-4, 1]$ 以 $2$ 美元移动到 $[-6, -1]$ - 将区间 $[-7, 5]$ 以 $11$ 美元移动到 $[-18, -6]$ 总花费为 $8 + 1 + 2 + 11 = 22$ 美元。 由 ChatGPT 4.1 翻译