問題
あなたの働いている建設会社は$ \ N \ $個のマンションを建設した。
建設会社は自分たちの建てたマンションの耐久性には自信をもっているが、地震による倒壊が心配になったので知り合いの地震専門家に頼んで$ \ X \ $年後までの地震の起こる回数$ \ M \ $と、今から何年後にに地震が起こるか$ \ y_i \ $とその地震の強さ$ \ p_i \ $を予測してもらった。
$i \ $番目のマンションの最初の耐久度は$ \ h_i \ $であり、強さ$ \ x \ $の地震が起こると全てのマンションの耐久度が$ \ x \ $減少し、マンションの耐久度が$ \ 0 \ $以下になるとマンションは倒壊してしまう。
しかし、地震の起こらなかった年はマンションの修復ができるため、$ 1 \ $年でマンションの耐久度が$ \ 1 \ $回復する。ただし、以下の点に注意すること。
・マンションの耐久度は最初の耐久度までしか回復しない。
・倒壊したマンションの耐久度は回復しない。
あなたは上司に$ \ X \ $年後には倒壊していないマンションがいくつあるのかを求めるプログラム作成するように指示を受けた。
入力
$N \ X \ M$ $h_1 \ h_2 \ldots h_N$ $y_1 \ p_1$ $y_2 \ p_2$ $\vdots$ $y_M \ p_M$
出力
$X \ $年後の倒壊していないマンションの数を出力せよ。出力の末尾には改行を入れること。
制約
- $1 \leq N \leq 10^5$
- $1 \leq X \leq 10^5$
- $0 \leq M \leq X$
- $1 \leq h_i \leq 10^9$
- $1 \leq y_i \leq X$
- $y_i \lt y_j \ (i \lt j)$
- $0 \leq p_i \leq 10^9$
- 入力は全て整数
入出力例
例１
入力
5 10 3 1 2 3 4 5 1 1 2 1 5 1
出力
3
例２
入力
5 100 1 3 1 5 8 2 5 10
出力
0
例３
入力
10 20 8 10 8 3 9 4 9 1 2 50 9 2 1 3 1 5 2 7 0 10 4 12 5 15 3 20 4
出力
2