Snow Boots Optimization

It's winter on the farm, and that means snow! There are \(N\) tiles on the path from the farmhouse to the barn, conveniently numbered \(1 \dots N\), and tile \(i\) is covered in \(f_i\) feet of snow. Farmer John starts off on tile \(1\) and must reach tile \(N\) to wake up the cows. Tile \(1\) is sheltered by the farmhouse roof, and tile \(N\) is sheltered by the barn roof, so neither of these tiles has any snow. But to step on the other tiles, Farmer John needs to wear boots!

In his foul‐weather backpack, Farmer John has \(B\) pairs of boots, numbered \(1 \dots B\). Pair \(i\) allows him to step in snow at most \(s_i\) feet deep and lets him move at most \(d_i\) tiles forward in one step. However, the boots are stacked in such a way that he can only access the topmost pair at any given time. At any moment, he may either put on the topmost pair of boots (discarding his old pair) or discard the topmost pair (thus exposing the next pair).

Farmer John can only change boots while standing on a tile. The boots he takes off and the boots he puts on must both be able to withstand at least the depth \(f\) of snow on that tile. (Intermediate pairs which are simply discarded do not need to satisfy this condition.)

Your task is to help Farmer John minimize waste by determining the minimum number of pairs of boots he must discard in order to reach the barn.

Note: You may assume that Farmer John is initially not wearing any boots, and since the farmhouse and barn are sheltered, \(f_1 = f_N = 0\).

inputFormat

The first line contains two integers \(N\) and \(B\), where \(2 \leq N \leq 250\) and \(1 \leq B \leq 250\).

The second line contains \(N\) non-negative integers \(f_1, f_2, \dots, f_N\) where \(0 \leq f_i \leq 10^9\). It is guaranteed that \(f_1 = f_N = 0\).

The next \(B\) lines each contain two integers \(s_i\) and \(d_i\) where \(0 \leq s_i \leq 10^9\) and \(1 \leq d_i \leq N-1\). The boots are given in the order in which they are stacked (the first boot is on top).

outputFormat

Output a single integer, the minimum number of boot pairs that Farmer John must discard in order to reach tile \(N\).

sample

5 3
0 2 8 3 0
3 2
8 3
0 1

0