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

输入 #1

3
-2 10
3 10
12 10

输出 #1

11

输入输出样例 #2

输入 #2

5
0 1000000000
0 1000000000
1 1000000000
2 1000000000
3 1000000000

输出 #2

4999999994

说明/提示

限制条件

• $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 翻译