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
pairs of
left and right gates, where each right gate is
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
-th pair of gates
occurs at distance
down the hill, with the horizontal position of the
<sup>th</sup> left gate
given by
. Each
gate is further down the hill than the previous gate (i.e.
<
for all
).
You may select from
pairs of skis, where the -th pair has speed . Your movement is governed by
the following rule: if you select a pair of skis with speed
, you move with a
constant downward velocity of metres per second.
Additionally, at any time you may move at a horizontal speed of
at most 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
, , and , separated by spaces, with
,
,
and .
The following lines
of input each contain two integers and , the horizontal and vertical
positions respectively of the -th left gate, with .
The next line of input contains an integer , the number of skis, with
.
The following lines
of input each contain one integer , the speed of the -th pair of skis, with .
Output Specification
If it is impossible to complete the race with any pair of
skis, print the line IMPOSSIBLE.
Otherwise, print the vertical speed 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
|
