택시 부르기

관광객 한 무리가 계곡에 있는 관광 지점 $n$개를 $p_1, p_2, \dots, p_n$ 순서 그대로 둘러본다. 이동 수단은 승용차, 인력거, 당나귀 수레처럼 종류가 여럿이고 모두 전화로 불러야 한다. 계곡 깊은 곳은 관광 지점에서만 전화가 터지므로 이동 수단은 관광 지점에서만 바꿀 수 있다.

$i$번째 구간은 $p_i$에서 $p_{i+1}$까지 가는 길이다. 길이는 $d_i$이고, 진행 방향을 직전 구간에서 $h_i$만큼 튼다. 첫 구간도 $h_1$만큼 튼 것으로 보므로 $i$번째 구간의 진행 방향은 $H_i = h_1 + h_2 + \cdots + h_i$이다.

$j$번째 종류의 기사는 다음 두 조건을 모두 만족할 때만 $p_x$에서 $p_y$까지 ($x < y$) 한 번에 태워 준다.

• 최소 거리: 이동 거리의 합 $d_x + d_{x+1} + \cdots + d_{y-1}$이 $dmin_j$ 이상이어야 한다. 이보다 짧으면 기사가 나설 만한 일이 아니다.
• 최대 방향 폭: 진행 방향 $H_x, H_{x+1}, \dots, H_{y-1}$ 중 최댓값에서 최솟값을 뺀 값이 $a_j$ 이하여야 한다. 기사는 곧게 가지 않는 길을 싫어한다.

여정 전체를 연속한 구간 묶음으로 나누고 묶음마다 기사를 한 번 부른다. 같은 종류를 다시 써도 되지만, 앞 기사가 그만두면 같은 종류라도 새로 불러야 하고 그만큼 호출 횟수가 늘어난다. $p_1$에서 출발해 $p_n$까지 주어진 순서대로 모두 방문하는 데 필요한 최소 호출 횟수를 구하라.

첫 줄에 이동 수단의 종류 수 $t$ ($1 \le t \le 200$)와 방문할 지점의 수 $n$ ($1 \le n \le 5 \times 10^4$)이 공백으로 구분되어 주어진다.

다음 $t$개의 줄에는 종류마다 음이 아닌 정수 두 개가 주어진다. 첫 번째 정수 $dmin_j$ ($0 \le dmin_j \le 10^6$)는 그 종류가 요구하는 최소 이동 거리이고, 두 번째 정수 $a_j$ ($0 \le a_j \le 3.6 \times 10^5$)는 그 종류가 허용하는 최대 방향 폭이다.

다음 $n - 1$개의 줄에는 $i$번째 구간의 길이 $d_i$ ($0 \le d_i \le 10^6$)와 방향 변화량 $h_i$ ($-1.8 \times 10^5 < h_i < 1.8 \times 10^5$)가 주어진다. $n = 1$이면 이 줄은 없다.

각도는 모두 1000분의 1도 단위이다.

$p_1$부터 $p_n$까지 주어진 순서대로 모두 방문하는 데 필요한 최소 호출 횟수를 한 줄에 출력한다. 방문할 방법이 없으면 IMPOSSIBLE을 출력한다. $n = 1$이면 이동하지 않아도 되므로 0을 출력한다.