É inverno na fazenda, e isso significa neve! Há $N$ ladrilhos no caminho da casa ao celeiro, numerados $1 \dots N$, e o ladrilho $i$ tem $f_i$ pés de neve.
Farmer John começa no ladrilho $1$ e deve chegar ao $N$ para acordar as vacas. O ladrilho $1$ é protegido pelo telhado da casa e o $N$ pelo do celeiro, então nenhum dos dois tem neve. Para pisar nos demais, ele precisa de botas!
Na mochila para mau tempo, há $B$ pares de botas, numerados $1 \dots B$. Alguns são mais resistentes, outros mais ágeis. O par $i$ permite pisar em neve de até $s_i$ pés de profundidade e avançar até $d_i$ ladrilhos por passo.
Infelizmente, só o par no topo fica acessível. A qualquer momento, ele pode calçá-lo, descartando o par antigo, ou descartar o par do topo para acessar o próximo.
Só pode trocar de botas estando sobre um ladrilho. Se houver $f$ pés de neve nele, tanto o par retirado QUANTO o par calçado devem suportar pelo menos $f$ pés de neve. Os pares intermediários descartados sem serem usados não precisam satisfazer essa restrição.
Para minimizar o desperdício, determine o menor número de pares que ele precisa descartar para chegar ao celeiro. Inicialmente, ele não está usando botas.
Entrada
A primeira linha contém os inteiros $N$ e $B$ separados por espaço ($2 \leq N,B \leq 250$).
A segunda contém $N$ inteiros separados por espaços. O inteiro de posição $i$ é $f_i$, a profundidade de neve no ladrilho $i$ ($0 \leq f_i \leq 10^9$). É garantido que $f_1 = f_N = 0$.
As próximas $B$ linhas contêm dois inteiros separados por espaço. O primeiro na linha $i+2$ é $s_i$, a máxima profundidade de neve para o par $i$. O segundo na linha $i+2$ é $d_i$, o tamanho máximo do passo para o par $i$. É garantido que $0 \leq s_i \leq 10^9$ e $1 \leq d_i \leq N-1$.
Os pares são descritos de cima para baixo: o par $1$ está no topo da mochila, e assim por diante.
Saída
Imprima um inteiro: o mínimo número de pares que precisa descartar. É garantido que ele pode chegar ao celeiro.
Exemplos
Entrada 1
10 4 0 2 8 3 6 7 5 1 4 0 2 3 4 2 3 4 7 1
Saída 1
2
Autores: Brian Dean e Dhruv Rohatgi