農場に冬が来て、雪が降りました！農家から納屋への道には $N$ 枚のタイルがあり、$1 \dots N$ と番号が付いています。タイル $i$ には深さ $f_i$ フィートの雪があります。

Farmer John はタイル $1$ から出発し、牛を起こすためタイル $N$ に着かなければなりません。タイル $1$ は農家の屋根、タイル $N$ は納屋の屋根で覆われているため、どちらにも雪はありません。しかし他のタイルを踏むにはブーツが必要です！

悪天候用のリュックには、$1 \dots B$ と番号が付いた $B$ 組のブーツがあります。より丈夫なものも、より動きやすいものもあります。具体的に、組 $i$ では深さ $s_i$ フィート以下の雪を踏め、一歩で前方へ最大 $d_i$ タイル進めます。

残念ながら、詰め方のため常に一番上の組しか取り出せません。いつでも一番上のブーツを履く（古い組を捨てる）か、一番上の組を捨てる（次の組が取り出せるようになる）ことができます。

ブーツを履き替えられるのはタイル上だけです。そのタイルに深さ $f$ フィートの雪があれば、脱ぐ組と履く組の両方が深さ $f$ フィート以上の雪に対応していなければなりません。途中で履かずに捨てる組にはこの制限はありません。

無駄を減らすため、Farmer John が納屋へ着くまでに捨てるブーツの組数の最小値を求めてください。最初はブーツを履いていないと仮定できます。

入力

最初の行には空白区切りの整数 $N$ と $B$ が与えられます（$2 \leq N,B \leq 250$）。

次の行には空白区切りの $N$ 個の整数が与えられます。$i$ 番目は $f_i$ で、タイル $i$ の雪の深さを表します（$0 \leq f_i \leq 10^9$）。$f_1 = f_N = 0$ が保証されます。

続く $B$ 行にはそれぞれ空白区切りの二整数が与えられます。行 $i+2$ の最初の整数は $s_i$ で、組 $i$ が踏める雪の最大深さです。行 $i+2$ の二番目は $d_i$ で、組 $i$ の最大歩幅です。$0 \leq s_i \leq 10^9$ と $1 \leq d_i \leq N-1$ が保証されます。

ブーツは上から下の順に記述され、組 $1$ がリュックの一番上にあります。

出力

捨てなければならないブーツの最小組数を整数一つで出力してください。納屋に到達できることが保証されます。

入出力例

入力 1

10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 1

出力 1

2

問題作成：Brian Dean、Dhruv Rohatgi