Slastičarnica

문제

There is a new bakery in town! Come and try delicious cakes from Dodo’s bakery!

The bakers have prepared $nn$ cakes, the $ii$-th of which has sweetness $a_{i}a\_i$. They are displayed on a long table in the given order. There are $qq$ people waiting in line to order the best cakes in town. Each of them has an order of the form: “I would like to buy $d_{i}d\_i$ cakes whose sweetnesses are at least $s_{i}s\_i$”.

Dorijan serves customers in a peculiar way. He will give $d_{i}d\_i$ continuous cakes from the table. To keep the table looking as nice as possible he will only give cakes from the left or the right edge of the table. He noticed that he cannot serve a lot of customers that way, so before serving a customer he will eat some cakes (possibly none) from the edges of the table.

If Dorijan cannot satisfy a customer, he will close the bakery for the day. What is the largest number of customers he can serve, before closing?

입력

The first line contains two integers $nn$, $qq$ (1 ≤ n ≤ 5\,000, 1 ≤ q ≤ 2 \cdot 10^5), the number of cakes and the number of people in the line.

The second line contains $nn$ numbers $a_{i}a\_i$ (1 ≤ a_i ≤ 10^9), where $a_{i}a\_i$ is the sweetness of the $ii$-th cake.

In each of the next $qq$ lines there are two integers $d_{i}d\_i$, $s_{i}s\_i$ (1 ≤ d_i ≤ n, 1 ≤ s_i ≤ 10^9), the order of the $ii$-th customer in line.

출력

In the first and only line output the number of customers Dorijan can serve.

힌트

Clarification of the third example: Dorijan first eats one cake from the left, then gives the next three cakes with sweetnesses $33$, $22$, and $55$ to the first customer. He then eats another cake from the left and gives the next two cakes with sweetnesses $44$ and $66$ to the second customer. The third customer gets a cake from the right with sweetness $11$ and the fourth gets the last cake with sweetness $22$. Dorijan unfortunately does not have more cakes, so the last customer goes home empty-handed.

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

4

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

2

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

4