겨울 데이트

어느덧 겨울이 도시에 찾아왔고, 도시의 중심가로 가는 경로에는 $N$ 개의 타일이 있습니다. 타일에는 $1 \dots N$로 번호가 매겨져 있고, $i$ 번 타일은 $f_i$ 피트의 눈으로 덮여 있습니다.

주환은 $1$ 번 타일에서 시작하여 도시의 중심가에 있는 $N$ 번 타일에 도착해서 여자친구를 만나야 합니다. $1$ 번 타일과 $N$ 번 타일은 건물 아래에 위치해있어 이 두 개의 타일에는 눈이 전혀 쌓이지 않았습니다. 그러나 다른 타일들을 밟기 위해서는 주환은 부츠를 꼭 신어야 합니다!

주환의 가방에는 $B$ 켤레의 부츠가 있습니다. 부츠는 $1 \dots B$로 번호가 매겨져 있습니다. 일부는 다른 것들보다 더 튼튼하지만, 일부는 다른 것들보다 더 민첩합니다. 예를 들면, $i$ 번 부츠는 주환이 최대 $s_i$ 피트의 눈에 들어갈 수 있게 해주며 한 걸음에 최대 $d_i$씩 앞으로 이동하게 합니다.

안타깝게도, 부츠들은 어느 시점에서라도 가장 위에 있는 켤레만 꺼낼 수 있도록 패킹되어 있습니다. 그래서 언제든지 주환은 가장 위에 있는 부츠를 신거나 (기존의 부츠를 버린다) 가장 위에 있는 부츠를 버립니다(새로운 부츠 켤레를 신습니다).

주환은 타일 위에 서 있을 때만 부츠를 바꿀 수 있습니다. 그 타일이 $f$ 피트의 눈으로 덮여 있다면, 그가 벗는 부츠와 신는 부츠 모두 최소 $f$ 피트의 눈을 견딜 수 있어야 합니다. 그가 착용하지 않고 버린 중간 켤레의 부츠는 이 제한을 충족시킬 필요가 없습니다.

주환이 약속 장소 타일에 도달할 수 있도록 버려야 하는 부츠의 최소 켤레 수를 결정하여 낭비를 최소화하는 데 도움을 주세요. 당신은 주환이 처음에는 부츠를 전혀 신고 있지 않다고 가정할 수 있습니다.

첫 번째 줄에는 두 개의 공백으로 구분된 정수 $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번 켤레는 주환의 백팩에서 가장 위에 있는 켤레이며, 그런 식으로 계속됩니다.

출력은 주환이 버려야 하는 부츠의 최소 켤레 수를 나타내는 하나의 정수로 구성되어야 합니다. 주환은 약속 장소까지 갈 수 있다는 것이 보장됩니다.