AT_abc219_h [ABC219H] Candles

在一条无限延伸的数轴上，放置着 $N$ 根蜡烛。第 $i$ 根蜡烛位于坐标 $X_i$，在时刻 $0$ 时长度为 $A_i$，并且已经点燃。被点燃的蜡烛每分钟长度减少 $1$，当长度变为 $0$ 时就会燃尽，此后长度不再变化。此外，被熄灭的蜡烛长度也不会再发生变化。 高桥君在时刻 $0$ 时位于坐标 $0$，每分钟最多可以移动 $1$ 的距离。如果高桥君所在的坐标正好有蜡烛，他可以将该位置所有的蜡烛同时熄灭（熄灭蜡烛所需时间可以忽略不计）。 请你求出高桥君采取最优行动时，从时刻 $0$ 到 $10^{100}$ 分钟后，所有剩余蜡烛长度的总和可能达到的最大值。

输入以如下格式从标准输入读入。 > $N$ $X_1$ $A_1$ $X_2$ $A_2$ $\cdots$ $X_N$ $A_N$

请输出答案。

## 限制条件 - $1 \leq N \leq 300$ - $-10^9 \leq X_i \leq 10^9$ - $1 \leq A_i \leq 10^9$ - 所有输入均为整数。 ## 样例解释 1 第 $3$ 根蜡烛位于坐标 $12$，无论高桥君如何行动，在他赶到之前这根蜡烛都会燃尽。对于剩下的 $2$ 根蜡烛，首先花 $2$ 分钟移动到坐标 $-2$，将第 $1$ 根蜡烛熄灭，然后再花 $5$ 分钟移动到坐标 $3$，将第 $2$ 根蜡烛熄灭。此后这些蜡烛的长度不再变化。此时各蜡烛剩余长度分别为 $10-2=8$ 和 $10-2-5=3$，剩余长度总和为 $8+3=11$，这是可能的最大值。因此，输出 $11$。 ## 样例解释 2 请注意，可能存在多个蜡烛在同一坐标的情况，且答案可能超出 $32$ 位整数范围。 由 ChatGPT 4.1 翻译