CF38E Let's Go Rolling!

在一条从左到右延伸的数轴上，$n$ 个弹珠位于坐标 $x_{1}, x_{2}, ..., x_{n}$ 上。我们假设弹珠的体积无限小，即在本题中每个弹珠都被视作质点。你可以在其中一些弹珠上插针，第 $i$ 个弹珠插针的花费为 $c_{i}$，$c_{i}$ 可能为负数。当你完成选择并插好针后，弹珠会按照如下规则向左滚动：若弹珠上插了针，则该弹珠不动；否则该弹珠一直向左滚动，直到遇到最近的一个有针的弹珠并停在那里。如果左侧没有任何有针的弹珠，则该弹珠会滚到左无穷远，这会导致你需要支付无穷大的罚款。如果没有弹珠滚向无穷远，则罚金包括两部分： - 所有插针弹珠的花费之和； - 每个弹珠移动距离的总和，即每个弹珠初始位置和最终位置之差的绝对值之和。 你的任务是选择在某些弹珠上插针，使得你需要支付的罚金尽可能小。

第一行包含一个整数 $n$（$1 \leq n \leq 3000$），表示弹珠的数量。接下来的 $n$ 行中，每一行包含两个整数 $x_{i}$ 和 $c_{i}$（$-10^{9} \leq x_{i}, c_{i} \leq 10^{9}$），分别表示第 $i$ 个弹珠的位置和在其上插针的花费。每组数据之间用空格隔开。每个描述单独一行。任意两个弹珠不会处于相同的位置。

输出一个整数，表示你需要支付的最小罚金。

由 ChatGPT 5 翻译