농장에 겨울이 왔고, 눈이 내렸습니다! 농가에서 헛간까지의 길에는 $1 \dots N$으로 번호가 매겨진 타일 $N$개가 있으며, 타일 $i$에는 깊이 $f_i$피트의 눈이 쌓여 있습니다.

Farmer John은 타일 $1$에서 출발해 소를 깨우러 타일 $N$에 도달해야 합니다. 타일 $1$은 농가 지붕, 타일 $N$은 헛간 지붕이 가려 주므로 둘 다 눈이 없습니다. 다른 타일을 밟으려면 장화를 신어야 합니다!

악천후용 배낭에는 $1 \dots B$로 번호가 매겨진 장화 $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+2$번째 줄의 둘째 정수는 장화 $i$의 최대 걸음 크기 $d_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