Snow Boots

Winter has arrived on the farm, and with it the snow. A path of $N$ tiles runs from the farmhouse to the barn, numbered $1$ through $N$, and tile $i$ is covered by $f_i$ feet of snow.

Farmer John starts on tile $1$ and has to reach tile $N$ to wake the cows. Tile $1$ sits under the farmhouse roof and tile $N$ sits under the barn roof, so neither one holds any snow. To step on any other tile, Farmer John needs boots.

His foul-weather backpack holds $B$ pairs of boots, numbered $1$ through $B$. Some pairs are sturdier and some are nimbler: pair $i$ lets him step in snow at most $s_i$ feet deep, and lets him move at most $d_i$ tiles forward in one step.

The boots are packed in a stack, so only the topmost pair is within reach. At any moment Farmer John can put on the topmost pair, which discards the pair he was wearing, or discard the topmost pair without wearing it, which exposes the pair below.

Farmer John changes boots only while standing on a tile. If that tile holds $f$ feet of snow, the pair he takes off and the pair he puts on must both withstand at least $f$ feet. A pair he discards without ever wearing it is free of this restriction.

Farmer John starts out wearing no boots. Find the smallest number of pairs he has to discard to reach the barn.

The first line contains two integers $N$ and $B$ separated by a space ($2 \leq N, B \leq 250$).

The second line contains $N$ integers separated by spaces. The $i$th of them is $f_i$, the depth of snow on tile $i$ ($0 \leq f_i \leq 10^9$). It is guaranteed that $f_1 = f_N = 0$.

Each of the next $B$ lines contains two integers separated by a space. Line $i+2$ holds $s_i$, the greatest snow depth pair $i$ can step in, and $d_i$, the greatest step size for pair $i$ ($0 \leq s_i \leq 10^9$, $1 \leq d_i \leq N-1$).

The pairs are listed from the top of the backpack downward, so pair $1$ is the topmost pair.

Print one integer, the smallest number of pairs Farmer John has to discard. Reaching the barn is always possible.