슬라럼

시간 제한1초메모리 제한128 MB

요약
깊이가 커지는 게이트 쌍들과 S개의 수직 속도가 주어질 때, 모든 게이트를 통과할 만큼 수평으로 빠르게 움직일 수 있는 가장 작은 속도를 찾아 출력하거나 IMPOSSIBLE을 출력한다.
난이도

보통10점 중 7점

유형
이분 탐색, 수학, 그리디, 구현
정답자
아직 제출이 없습니다

문제

스키 슬라럼 경기에 출전하며, 경기에 가장 알맞은 스키 한 켤레를 골라야 합니다. 코스에는 NN개의 관문 쌍이 있습니다. 각 쌍은 왼쪽 관문과 오른쪽 관문으로 이루어지며, 오른쪽 관문은 대응하는 왼쪽 관문에서 정확히 오른쪽으로 WW미터 떨어져 있습니다. 왼쪽 관문의 왼쪽으로도, 오른쪽 관문의 오른쪽으로도 지나갈 수 없습니다. ii번째 관문 쌍은 언덕 아래로 수직 거리 yiy_i 지점에 있으며, 그 왼쪽 관문의 수평 위치는 xix_i입니다(따라서 오른쪽 관문은 xi+Wx_i + W에 있습니다). 모든 관문은 이전 관문보다 언덕 아래쪽에 있습니다. 즉, 모든 ii에 대해 yi<yi+1y_i < y_{i+1}입니다.

SS개의 스키 쌍 중 하나를 고를 수 있으며, jj번째 쌍의 속도는 sjs_j입니다. 속도가 sjs_j인 스키를 고르면 초당 sjs_j미터의 일정한 수직 속도로 내려갑니다. 이와 별개로, 어느 순간에나 수평 방향으로는 초당 최대 vhv_h미터의 속도로 이동할 수 있습니다. 출발과 도착의 수평 위치는 자유롭게 정할 수 있습니다.

모든 관문을 통과하여 코스를 가장 짧은 시간에 완주하게 해 주는 스키 쌍이 무엇인지 구하세요.

입력

첫째 줄에 세 정수 WW, vhv_h, NN이 공백으로 구분되어 주어집니다. 1≤W≤1081 \le W \le 10^8, 1≤vh≤1061 \le v_h \le 10^6, 1≤N≤1051 \le N \le 10^5입니다.

다음 NN개의 줄에는 각각 두 정수 xix_i와 yiy_i가 주어지며, 이는 ii번째 왼쪽 관문의 수평 위치와 수직 위치입니다. 1≤xi,yi≤1081 \le x_i, y_i \le 10^8입니다.

그다음 줄에는 스키 쌍의 개수 SS가 주어집니다. 1≤S≤1061 \le S \le 10^6입니다.

다음 SS개의 줄에는 각각 한 정수 sjs_j가 주어지며, 이는 jj번째 스키 쌍의 속도입니다. 1≤sj≤1061 \le s_j \le 10^6입니다.

출력

어떤 스키 쌍으로도 코스를 완주할 수 없다면 IMPOSSIBLE을 출력합니다. 그렇지 않으면 코스를 가장 짧은 시간에 완주하게 해 주는 스키 쌍의 수직 속도 sjs_j를 출력합니다.

예제1

  1. 예제 1

    입력
    3 2 3
    1 1
    5 2
    1 3
    3
    3
    2
    1
    
    예상 출력
    2