Problem G
Slalom 2
You may select from $S$ pairs of skis, where the $j$-th pair has speed $s_{j}$. Your movement is governed by the following rule: if you select a pair of skis with speed $s_{j}$, you move with a constant downward velocity of $s_{j}$ metres per second. Additionally, at any time you may move at a horizontal speed of at most $v_{h}$ metres per second.
You may start and finish at any two horizontal positions. Determine which pair of skis will allow you to get through the race course, passing through all the gates, in the shortest amount of time.
Input Specification
The first line of input contains the three integers $W$, $v_{h}$, and $N$, separated by spaces, with $1 <= W <= 10^8$, $1 \leq v_{h} \leq 10^6$, and $1 \leq N \leq 10^5$.
The following $N$ lines of input each contain two integers $x_{i}$ and $y_{i}$, the horizontal and vertical positions respectively of the $i$-th left gate, with $1 \leq x_{i},\, y_{i} \leq 10^8$.
The next line of input contains an integer $S$, the number of skis, with $1 \leq S \leq 10^6$.
The following $S$ lines of input each contain one integer $s_{j}$, the speed of the $j$-th pair of skis, with $1 \leq s_{j} \leq 10^6$.
Output Specification
If it is impossible to complete the race with any pair of skis, print the line IMPOSSIBLE. Otherwise, print the vertical speed $s_{j}$ of the pair of skis that allows you to get through the race course in the shortest time.
Sample Input 1 | Sample Output 1 |
---|---|
3 2 3 1 1 5 2 1 3 3 3 2 1 |
2 |
Sample Input 2 | Sample Output 2 |
---|---|
3 2 3 1 1 5 2 1 3 1 3 |
IMPOSSIBLE |