Score : $600$ points

问题描述

在一条无限数轴上有 $N$ 支蜡烛。第 $i$ 支蜡烛位于坐标 $X_i$ 处，在时间 $0$ 时，其长度为 $A_i$ 并且处于燃烧状态。每过一分钟，燃烧中的蜡烛长度减少 $1$。当长度减至 $0$ 时，蜡烛燃尽，并且之后其长度不再改变。另外，未点燃的蜡烛长度不会发生变化。

高桥在时间 $0$ 时位于坐标 $0$ 处。每分钟，他最多可以移动距离 $1$。如果当前位置存在蜡烛，他可以选择熄灭那支蜡烛。（如果该位置有多支蜡烛，他可以将它们全部熄灭。）熄灭一支蜡烛所需的时间可以忽略不计。

请找出在时间 $0$ 后的 $10^{100}$ 分钟时，通过高桥采取最优行动策略所能达到的剩余蜡烛最大总长度。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are $N$ candles on an infinite number line. The $i$-th candle is at the coordinate $X_i$. At time $0$, it has a length of $A_i$ and is lit. Each minute, the length of a lit candle decreases by $1$. When the length becomes $0$, it burns out, and its length does not change after that. Additionally, the length of an unlit candle does not change.

Takahashi is at the coordinate $0$ at time $0$. Each minute, he can move a distance of at most $1$. If there is a candle at his current coordinate, he can put out that candle. (If there are multiple candles there, he can put out all of them.) The time it takes to put out a candle is negligible.

Find the maximum possible total length of the candles remaining at $10^{100}$ minutes after time $0$, achieved by Takahashi's optimal course of actions.

Constraints

• $1 \leq N \leq 300$
• $-10^9 \leq X_i \leq 10^9$
• $1 \leq A_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

$X_1$ $A_1$

$X_2$ $A_2$

$:$

$X_N$ $A_N$

Output

Print the answer.

Sample Input 1

3
-2 10
3 10
12 10

Sample Output 1

11

The third candle, which is at coordinate $12$, will burn out before Takahashi puts it out, regardless of Takahashi's behavior.
For the other two candles, if he goes to coordinate $-2$ in two minutes to put out the first and then goes to coordinate $3$ in five minutes to put out the second, the lengths of those candles will not change after that. The lengths of those candles remaining are $10-2=8$ and $10-2-5=3$, for a total of $8+3=11$, which is the maximum that can be achieved. Thus, print $11$.

Sample Input 2

5
0 1000000000
0 1000000000
1 1000000000
2 1000000000
3 1000000000

Sample Output 2

4999999994

Note that two or more candles may occupy the same coordinate and that the answer may not fit into a $32$-bit integer.

update @ 2024/3/10 09:42:53