農場的冬天到了，下雪了！從農舍到穀倉的路上有 $N$ 塊地磚，編號為 $1 \dots N$，地磚 $i$ 上有 $f_i$ 英尺深的積雪。

Farmer John 從地磚 $1$ 出發，必須到達地磚 $N$ 去叫醒乳牛。地磚 $1$ 被農舍屋頂遮蔽，地磚 $N$ 被穀倉屋頂遮蔽，所以這兩塊地磚上都沒有雪。但踩上其他地磚時，Farmer John 必須穿靴子！

在惡劣天氣專用背包裡，Farmer John 有 $B$ 雙靴子，編號為 $1 \dots B$。有些靴子更耐用，有些更靈活。具體而言，第 $i$ 雙靴子允許 FJ 踩在至多 $s_i$ 英尺深的雪上，每一步至多向前移動 $d_i$ 塊地磚。

不幸的是，靴子的堆放方式使 Farmer John 在任何時候都只能拿到最上面的一雙。因此，他隨時可以穿上最上面的靴子（丟棄舊靴子），或者丟棄最上面的靴子（使下一雙可取用）。

Farmer John 只能站在地磚上換靴子。如果該地磚上有 $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$ 雙是 FJ 背包裡最上面的一雙，依此類推。

輸出格式

輸出一個整數，表示 Farmer John 所需丟棄的靴子雙數的最小值。保證他能夠到達穀倉。

範例

輸入格式 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