Prefix-Suffix Deletion Game

You are given an array \(a_1, a_2, \ldots, a_n\) of integers and a sequence of \(q\) operations. The \(i\)-th operation is described by two numbers \(d_i\) and \(s_i\). In each operation the following procedure is performed:

1. Before performing the operation, you may choose to delete an arbitrary-length prefix or suffix of the current array (the removed block may be empty).
2. Then, you must delete a prefix or suffix of length \(d_i\), with the additional condition that every element in the deleted block is at least \(s_i\) (i.e. every element \(\ge s_i\)).

If at any point an operation cannot be performed (that is, neither from the prefix nor the suffix can you find a contiguous block of length \(d_i\) where every element is \(\ge s_i\)), then that operation and all subsequent operations are abandoned.

Your task is to determine the maximum number of operations that can be performed by strategically choosing which extra prefix or suffix to delete before each operation.

Note: In the deletion (step 2) you are required to delete exactly \(d_i\) contiguous elements from one end (either the beginning or the end) of the current array. In step 1 you are allowed to remove an arbitrary number of elements from one end (prefix or suffix) to help satisfy the condition.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n, q \le\text{small constraints})\) — the number of elements in the array and the number of operations, respectively.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the array.

Each of the following \(q\) lines contains two integers \(d_i\) and \(s_i\), describing an operation.

outputFormat

Output a single integer: the maximum number of operations that can be performed.

sample

5 3
5 4 3 6 7
1 3
1 4
1 5

3