You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一个 MP3 播放器，这个播放器如果连续 $t$ 秒没有任何操作就会自动休眠。在休眠期间，任何按键都不会起到按键本身的作用，而只会终止休眠。

例如，假设 $t=5$ 且播放器当前处于锁定状态。然后进行如下 $4$ 步操作：

• 按下 A，停顿 $3$ 秒；
• 按下 B，停顿 $5$ 秒；
• 按下 C，停顿 $6$ 秒；
• 按下 D。

这些操作过后，实际执行的只有 B C。注意，在按 C 和按 D 之间播放器已经休眠了。

这个 MP3 还有两个音量控制键 + -，分别为将音量调高一个单位或降低一个单位。音量只能为介于 $0\sim V_{\max}$ 之间的整数，即如果音量为 $0$ 时按 - 或音量为 $V_{\max}$ 时按 +，音量均不发生改变。

刚开始你并不知道 $t$ 的值，便想通过实验来得出。

播放器刚开始是休眠的。你会从某一个音量 $V_1$ 开始，经过 $n$ 次操作得到音量 $V_2$，操作的具体步骤已经给出，每次操作形如 +/- $C_i$，表示在距离实验开始 $C_i$ 秒时按下 + 或 -。

不幸的是，你也不知道 $V_1$ 的值，现在，你需要找出符合实验操作的 $t$ 的最大值，并输出相应的 $V_1$ 。

输入格式

输入第一行三个整数 $n,V_{\max},V_2$。

接下来的 $n$ 行，每行为一个字符 $x_i$ 和一个整数 $C_i$（有空格隔开）。$x_i$ 为 + 或 -，表示调高音量或者降低音量。

$C_i$ 表示距离实验开始 $C_i$ 秒后进行该操作，保证 $C_i$ 在输入中严格递增。

输出格式

输出一行两个整数，为 $t,V_1$ 的值。

如果有多种可能的方案，输出 $t$ 的最大的那一组；如果 $t$ 最大时同样有多种方案，输出 $V_1$ 最大的一组。

如果 $t$ 可以任意大，则输出 infinity。

请注意，不存在无解的情况。因为有一个方案：$t=0$ 一定存在。在这种情况下所有的按键都无法发挥作用，所以 $V_1=V_2$。

6 4 3
- 0
+ 8
+ 9
+ 13
- 19
- 24

5 4

3 10 10
+ 1
+ 2
+ 47

infinity

提示

【样例解释】

样例 1 解释

当 $t=5$ 时，按键的情况为；解锁,解锁,+,+,解锁,-。

此时对于 $V_1\in \{2,3,4\}$，可以得到 $V_2=3$。但是要输出最大的 $V_1$。

当 $t\geq 6$ 时，最后两个按键都会发挥正常的作用，也就是连续下调两个音量。此时结果无法为 $V_2=3$，故 $t_{\max}=5$。

样例 2 解释

当 $V_1=10$ 时，任意的 $t$ 都能满足条件。

【数据规模与约定】

• 对于 $40\%$ 的数据，保证 $n\le 4000$；
• 对于 $70\%$ 的数据，保证 $n\times V_{\max}\le 4\times 10^5$；
• 对于 $100\%$ 的数据，保证 $2\le n\le 10^5$，$2\le V_{\max}\le 5000$，$0<C_i<2\times 10^9$，$0\le V_2\le V_{\max}$，$x_i\in\{\texttt{+}, \texttt{-} \}$。

【说明】

题目译自 CEOI 2010 day 2 T1 mp3player。

翻译版权为题目提供者