MP3 Player Volume Experiment

An MP3 player automatically goes to sleep if there is no operation for t consecutive seconds. When the player is asleep (locked), any key press will only wake it up, and its normal function will not occur. When it is awake, if the gap between the current key press and the previous key press is no more than t seconds then the key’s function is executed; otherwise the player has already fallen asleep and the key press only wakes it up (with no volume change).

The player has two volume‐control keys: “+” increases the volume by 1 (if the volume is less than \(V_{\max}\)); “–” decreases the volume by 1 (if the volume is greater than 0). The volume is always an integer between 0 and \(V_{\max}\). Initially the player is asleep and its starting volume \(V_1\) is unknown. An experiment is performed by pressing keys at specific times. The first press always wakes the device but does not change the volume. For each subsequent operation at time \(C_i\):

• If the time gap from the previous press is \(\le t\), then the key is executed (adjusting the volume according to the pressed key and obeying the boundaries).
• If the gap is greater than \(t\), then the device has fallen asleep and the key press only wakes the device (and does not affect the volume).

After all operations, the final volume is \(V_2\). Given the sequence of operations (each specified as a key and a time \(C_i\)) and the value \(V_2\), your task is to determine the maximum possible integer value of \(t\) such that there exists an initial volume \(V_1\) (with \(0\le V_1\le V_{\max}\)) producing the final volume \(V_2\) when the operations are simulated as above. Then, output the corresponding initial volume \(V_1\) (if multiple \(V_1\) are possible, output the smallest one).

Note: All time values are in seconds, and the operations are given in chronological order. When an operation is executed, the volume changes subject to the constraint that it remains in the range \([0,V_{\max}]\).

For example, suppose \(t=5\) and the player is locked initially. Consider the following four operations:

• Press a key at \(C_1=1\) sec (wakes the player, no volume change);
• Press a key at \(C_2=3\) sec (gap = 2, executed since \(2\le5\));
• Press a key at \(C_3=8\) sec (gap = 5, executed since \(5\le5\));
• Press a key at \(C_4=14\) sec (gap = 6, not executed since \(6>5\), only wakes the player).

In this case, only the second and third operations affect the volume. Using the proper adjustments with volume limits, one may be able to deduce a unique maximum \(t\) and an initial volume \(V_1\) that lead to the final volume \(V_2\>.

inputFormat

The input begins with a line containing three integers: n (the number of operations), Vmax (the maximum volume), and V2 (the final volume after the operations).

Then follow n lines. Each line contains an operation in the format:

sign time

where sign is either + (to increase volume) or - (to decrease volume), and time is an integer (in seconds) representing the time when the button is pressed. The operations are given in chronological order.

outputFormat

Output a single integer: the initial volume \(V_1\) corresponding to the maximum valid value of \(t\) for which the experiment can be explained. If multiple initial volumes are possible, output the smallest one.

sample

5 10 5
+ 1
+ 3
- 5
+ 6
- 10

5