Description

There is an MP3 player. If there is no operation for $t$ consecutive seconds, it will automatically go to sleep. During sleep, any key press will not perform its own function, but will only wake the player up (i.e., end the sleep).

For example, suppose $t=5$ and the player is currently locked. Then perform the following 4 steps:

• Press A, wait for $3$ seconds.
• Press B, wait for $5$ seconds.
• Press C, wait for $6$ seconds.
• Press D.

After these operations, the only keys that actually take effect are B and C. Note that the player has already gone to sleep between pressing C and pressing D.

This MP3 player also has two volume control keys + and -, which increase the volume by 1 unit or decrease it by 1 unit, respectively. The volume can only be an integer between $0$ and $V_{\max}$. That is, if the volume is $0$ and you press -, or if the volume is $V_{\max}$ and you press +, the volume does not change.

At first, you do not know the value of $t$, and you want to determine it through an experiment.

The player is sleeping at the beginning. You will start from some volume $V_1$, and after $n$ operations you obtain volume $V_2$. The exact operations are given. Each operation is of the form +/- $C_i$, meaning that you press + or - at time $C_i$ seconds after the experiment starts.

Unfortunately, you also do not know the value of $V_1$. Now, you need to find the maximum possible value of $t$ that is consistent with the experiment, and output the corresponding $V_1$.

Input Format

The first line contains three integers $n, V_{\max}, V_2$.

The next $n$ lines each contain a character $x_i$ and an integer $C_i$ (separated by a space). $x_i$ is + or -, meaning increasing or decreasing the volume.

$C_i$ means that the operation is performed $C_i$ seconds after the experiment starts. It is guaranteed that $C_i$ is strictly increasing in the input.

Output Format

Output one line with two integers, the values of $t$ and $V_1$.

If there are multiple possible solutions, output the one with the largest $t$. If there are still multiple solutions when $t$ is maximal, output the one with the largest $V_1$.

If $t$ can be arbitrarily large, output infinity.

Please note that there is always at least one solution. Because the solution $t=0$ always exists. In this case, none of the key presses can take effect, so $V_1=V_2$.

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

5 4

3 10 10
+ 1
+ 2
+ 47

infinity

Hint

Sample Explanation

Sample 1 Explanation

When $t=5$, the keys behave as: unlock, unlock, +, +, unlock, -.

At this time, for $V_1\in \{2,3,4\}$, we can obtain $V_2=3$. But you should output the largest $V_1$.

When $t\geq 6$, the last two key presses will both work normally, i.e., the volume is decreased twice in a row. Then the result cannot be $V_2=3$, so $t_{\max}=5$.

Sample 2 Explanation

When $V_1=10$, any $t$ can satisfy the condition.

Constraints

• For $40\%$ of the testdata, it is guaranteed that $n\le 4000$.
• For $70\%$ of the testdata, it is guaranteed that $n\times V_{\max}\le 4\times 10^5$.
• For $100\%$ of the testdata, it is guaranteed that $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{-}\}$.

Notes

This problem is translated from CEOI 2010 day 2 T1 mp3player.

The translation copyright belongs to the problem provider

Translated by ChatGPT 5