슬라스티차르니차

새로 문을 연 빵집이 동네에 생겼습니다! 도도 빵집의 맛있는 케이크를 와서 맛보세요!

제빵사들이 케이크 $n$개를 준비했습니다. $i$번째 케이크의 달콤함은 $a_i$입니다. 케이크는 주어진 순서대로 긴 테이블 위에 진열되어 있습니다. 동네에서 가장 좋은 케이크를 주문하려고 $q$명이 줄을 서 있습니다. 각 손님의 주문은 "달콤함이 $s_i$ 이상인 케이크 $d_i$개를 사고 싶습니다"라는 형식입니다.

도리안은 독특한 방식으로 손님을 응대합니다. 테이블에서 연속된 케이크 $d_i$개를 건넵니다. 테이블을 최대한 깔끔하게 유지하려고 테이블의 왼쪽 끝이나 오른쪽 끝에 있는 케이크만 건넵니다. 이 방식으로는 많은 손님을 응대할 수 없다는 것을 알게 된 도리안은, 손님을 응대하기 전에 테이블 양 끝에서 케이크를 몇 개(0개일 수도 있음) 먹습니다.

도리안이 손님의 주문을 맞출 수 없으면 그날 빵집 문을 닫습니다. 문을 닫기 전까지 응대할 수 있는 손님은 최대 몇 명입니까?

첫째 줄에 케이크 개수 $n$과 줄을 선 사람 수 $q$가 주어집니다 ($1 \le n \le 5000$, $1 \le q \le 2 \cdot 10^5$).

둘째 줄에는 $n$개의 수 $a_i$ ($1 \le a_i \le 10^9$)가 주어집니다. 여기서 $a_i$는 $i$번째 케이크의 달콤함입니다.

이어지는 $q$개의 줄에는 각각 두 정수 $d_i$, $s_i$ ($1 \le d_i \le n$, $1 \le s_i \le 10^9$)가 주어지며, 이는 줄에서 $i$번째 손님의 주문입니다.

첫 번째이자 유일한 줄에 도리안이 응대할 수 있는 손님 수를 출력합니다.

세 번째 예제에 대한 설명: 도리안은 먼저 왼쪽에서 케이크 하나를 먹고, 다음 케이크 세 개(달콤함 $3$, $2$, $5$)를 첫 번째 손님에게 줍니다. 이어서 왼쪽에서 케이크 하나를 더 먹고, 다음 케이크 두 개(달콤함 $4$, $6$)를 두 번째 손님에게 줍니다. 세 번째 손님은 오른쪽 끝의 케이크(달콤함 $1$)를 받고, 네 번째 손님은 마지막 케이크(달콤함 $2$)를 받습니다. 도리안에게 남은 케이크가 없으므로 마지막 손님은 빈손으로 돌아갑니다.