Call a Cab

A group of tourists visits $n$ points $p_1, p_2, \dots, p_n$ in a valley, in exactly that order. Transportation comes in several types (car, rickshaw, donkey cart), and every type is available on call only. Deep in the valley the phone works at the points and nowhere else, so the type of transportation can change only at a point.

Segment $i$ runs from $p_i$ to $p_{i+1}$. Its length is $d_i$, and it turns the heading by $h_i$ from the previous segment. The first segment counts as a turn of $h_1$ as well, so the heading of segment $i$ is $H_i = h_1 + h_2 + \cdots + h_i$.

A driver of type $j$ takes the group from $p_x$ to $p_y$ ($x < y$) in one ride only when both conditions hold.

• Minimum distance: the total distance $d_x + d_{x+1} + \cdots + d_{y-1}$ is at least $dmin_j$. A shorter ride is not worth the driver's time.
• Maximum heading range: the largest of the headings $H_x, H_{x+1}, \dots, H_{y-1}$ minus the smallest one is at most $a_j$. Drivers find anything other than going straight annoying.

Split the whole itinerary into consecutive groups of segments and call one driver for each group. The same type may be used again, but once a driver has had enough you hail a new one, and that adds another call even when the type is the same. Find the minimum number of calls needed to start at $p_1$ and visit every point up to $p_n$ in the given order.

The first line has the number of transportation types $t$ ($1 \le t \le 200$) and the number of points $n$ ($1 \le n \le 5 \times 10^4$), separated by a space.

Each of the next $t$ lines describes one type with two non-negative integers. The first integer $dmin_j$ ($0 \le dmin_j \le 10^6$) is the minimum distance that type requires, and the second integer $a_j$ ($0 \le a_j \le 3.6 \times 10^5$) is the maximum heading range it allows.

Each of the next $n - 1$ lines has the length $d_i$ ($0 \le d_i \le 10^6$) and the turn $h_i$ ($-1.8 \times 10^5 < h_i < 1.8 \times 10^5$) of segment $i$. There are no such lines when $n = 1$.

All angles are given in thousandths of a degree.

Print one line with the minimum number of calls needed to visit $p_1$ through $p_n$ in the given order. Print IMPOSSIBLE when no such split exists. Print 0 when $n = 1$, because no travel is needed.