Problem Description

Given a sequence of numbers \(a_1, \ldots, a_n\) and \(q\) operations, each operation is of the form "delete a prefix or suffix of length \(d_i\) such that all elements in the prefix or suffix are greater than or equal to \(s_i\)." Before each operation, you can choose an arbitrary length prefix or suffix (can be empty) and delete it. If an operation cannot be performed, all subsequent operations are stopped. Determine the maximum number of operations that can be performed.

Input Format

The first line contains two positive integers \(n, q\) (\(1 \le n \le 5,000, 1 \le q \le 2 \cdot 10^5\)), representing the length of the sequence and the number of operations.

The second line contains \(n\) positive integers \(a_i\) (\(1 \le a_i \le 10^9\)), representing the sequence.

The next \(q\) lines each contain two integers \(d_i, s_i\) (\(1 \le d_i \le n, 1 \le s_i \le 10^9\)), representing an operation.

Output Format

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

Sample Input and Output

Sample Input #1

5 6
1 2 3 4 5
1 1
1 2
1 3
1 4
1 6
1 5

Sample Output #1

4

Sample Input #2

5 3
1 3 2 2 1
3 1
1 3
2 2

Sample Output #2

2

Sample Input #3

9 5
1 3 2 5 1 4 6 2 1
3 2
2 3
1 1
1 2
1 1

Sample Output #3

4

Notes

Explanation of Sample #3:

First, delete the prefix \((1)\), then perform the first operation, deleting the prefix \((3, 2, 5)\). The sequence becomes \((1, 4, 6, 2, 1)\).

Then delete the prefix \((1)\), then perform the second operation, deleting the prefix \((4, 6)\), the sequence becomes \((2, 1)\).

Then do not delete any prefix or suffix, then perform the third operation, deleting the suffix \((1)\), the sequence becomes \((2)\).

Then do not delete any prefix or suffix, then perform the fourth operation, deleting the only remaining \((2)\), the sequence becomes empty.

The last operation cannot be completed because the sequence is empty, so the operations stop.

Thus, a total of four operations are performed.

见题面 Input 部分

见题面 Output 部分