Slalom 2 – Kattis, Kattis (original) (raw)

Hide

You are competing in a ski slalom, and you need to select the best skis for the race. The format of the race is that there are NNN pairs of left and right gates, where each right gate is WWW metres to the right of its corresponding left gate, and you may neither pass to the left of the left gate nor to the right of the right gate. The$i$-th pair of gates occurs at distance yiy_{i}yi down the hill, with the horizontal position of the iii^th left gate given by xix_{i}xi. Each gate is further down the hill than the previous gate (i.e.$y_{i}$ < yi+1y_{i+1}yi+1 for all iii).

You may select from SSS pairs of skis, where the jjj-th pair has speed sjs_{j}sj. 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 sjs_{j}sj metres per second. Additionally, at any time you may move at a horizontal speed of at most vhv_{h}vh 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$, vhv_{h}vh, and NNN, separated by spaces, with$1 <= W <= 10^8$,$1 \leq v_{h} \leq 10^6$, and 1leqNleq1051 \leq N \leq 10^51leqNleq105.

The following NNN lines of input each contain two integers xix_{i}xi and yiy_{i}yi, the horizontal and vertical positions respectively of the iii-th left gate, with 1leqxi,,yileq1081 \leq x_{i},\, y_{i} \leq 10^81leqxi,,yileq108.

The next line of input contains an integer SSS, the number of skis, with$1 \leq S \leq 10^6$.

The following SSS lines of input each contain one integer sjs_{j}sj, the speed of the jjj-th pair of skis, with 1leqsjleq1061 \leq s_{j} \leq 10^61leqsjleq106.

Output Specification

If it is impossible to complete the race with any pair of skis, print the line IMPOSSIBLE. Otherwise, print the vertical speed sjs_{j}sj of the pair of skis that allows you to get through the race course in the shortest time.

Please log in to submit a solution to this problem

Log in

You haven't made any submissions on this problem yet.