눈길 부츠

농장에 겨울이 왔고 눈이 쌓였다. 농가에서 헛간까지 이어지는 길에는 타일 $N$개가 $1$번부터 $N$번까지 놓여 있고, $i$번 타일에는 눈이 $f_i$피트만큼 쌓여 있다.

농부 존은 $1$번 타일에서 출발해 젖소를 깨우러 $N$번 타일까지 가야 한다. $1$번 타일은 농가 지붕 아래에, $N$번 타일은 헛간 지붕 아래에 있어서 두 타일에는 눈이 없다. 나머지 타일을 밟으려면 부츠를 신어야 한다.

방한 배낭에는 부츠 $B$켤레가 $1$번부터 $B$번까지 들어 있다. 어떤 부츠는 더 튼튼하고 어떤 부츠는 더 날쌔다. $i$번 부츠를 신으면 깊이가 최대 $s_i$피트인 눈까지 밟을 수 있고, 한 걸음에 최대 $d_i$칸까지 앞으로 갈 수 있다.

부츠는 차곡차곡 쌓여 있어서 맨 위 한 켤레에만 손이 닿는다. 존은 언제든지 맨 위 부츠를 신을 수 있고, 이때 신고 있던 부츠는 버린다. 맨 위 부츠를 신지 않고 그대로 버려서 그 아래 부츠를 꺼낼 수도 있다.

부츠는 타일 위에 서 있을 때만 갈아 신는다. 그 타일에 눈이 $f$피트 쌓여 있다면 벗는 부츠와 새로 신는 부츠 모두 깊이 $f$피트 이상을 견뎌야 한다. 한 번도 신지 않고 버리는 부츠는 이 조건을 지키지 않아도 된다.

처음에 존은 부츠를 신고 있지 않다. 헛간에 도착하려면 부츠를 최소 몇 켤레 버려야 하는지 구하시오.

첫째 줄에 정수 $N$과 $B$가 공백으로 구분되어 주어진다 ($2 \leq N, B \leq 250$).

둘째 줄에 정수 $N$개가 공백으로 구분되어 주어진다. $i$번째 정수는 $i$번 타일에 쌓인 눈의 깊이 $f_i$이다 ($0 \leq f_i \leq 10^9$). $f_1 = f_N = 0$임이 보장된다.

다음 $B$개 줄에는 각각 정수 두 개가 공백으로 구분되어 주어진다. $i+2$번째 줄의 첫 번째 정수는 $i$번 부츠가 밟을 수 있는 눈의 최대 깊이 $s_i$이고, 두 번째 정수는 $i$번 부츠의 최대 보폭 $d_i$이다 ($0 \leq s_i \leq 10^9$, $1 \leq d_i \leq N-1$).

부츠는 배낭 위쪽부터 아래쪽 순서로 주어지므로 $1$번 부츠가 맨 위에 있다.

버려야 하는 부츠의 최소 켤레 수를 정수 하나로 출력한다. 헛간까지 갈 수 있음이 보장된다.