Problem D
Fake It `Til You Make It

Fluttershy has been put in charge of a high-end boutique in Manehattan, and she needs to deal with the customers that come in.

It is well-known that Fluttershy is, well, very shy. So shy, in fact, that the only time she feels comfortable dealing with a customer is when she is wearing the same type of clothing as that customer! When she wears a particular type of clothing, she is able to assume the customer’s personality and make a sale. There are $M$ types of clothing customers can wear.

She knows that $N$ customers will come today. The $i^\text {th}$ customer wears clothing of type $C_ i$ and will arrive exactly $T_ i$ moments of time after the opening of the shop. The citizens of Manehattan are all snooty and expect nothing but the speediest service, so if Fluttershy is not ready to serve them the moment they arrive, they will immediately leave. On the other hoof, Fluttershy is a very efficient salespony; we can assume that Fluttershy can make a sale in zero time. (This also means that if multiple customers arrive at the same moment of time, Fluttershy can serve all of them.)

Originally, Fluttershy is not wearing any clothing. To wear some clothing, she needs to follow the following process:

• To put on clothing of type $i$, she needs to first ensure that she is not wearing any clothing. Then, she goes to the dressing room and takes $P_ i$ moments of time to put on the clothing. (That is, if she starts to put on clothing at time $t$, she is ready by time $t + P_ i$.)

• To remove clothing of type $i$, she goes to the dressing room and takes $R_ i$ moments of time to remove the clothing. (That is, if she starts to remove clothing at time $t$, she has removed it by time $t + R_ i$ and can immediately start to put on another clothing.)

What is the maximum number of ponies she can serve?

Input

The first line of input contains two integers, $N$ ($1 \leq N \leq 200\, 000$) and $M$ ($1 \leq M \leq N$), the number of customers that will arrive today, and the number of different types of clothing customers can wear, respectively.

The second line of input contains $M$ integers, $P_1, P_2, \dots , P_ M$ ($1 \leq P_ i \leq 10^{18}$), the required moments of time to put on each type of clothing.

The third line of input contains $M$ integers, $R_1, R_2, \dots , R_ M$ ($1 \leq R_ i \leq 10^{18}$), the required moments of time to remove each type of clothing.

The next $N$ lines of input contain the descriptions of the customers. In particular, the $i^\text {th}$ of these lines contains two integers $C_ i$ ($1\leq C_ i \leq M$) and $T_ i$ ($1 \leq T_ i \leq 10^{18}$), denoting that the $i^\text {th}$ customer is of type $C_ i$ and will arrive exactly $T_ i$ moments of time after the opening of the shop.

It is guaranteed that for all positive integers $i < N$, $T_ i \leq T_{i+1}$, and for all positive integers $k \leq M$, there exists some $j$ such that $C_ j = k$.

Output

Output a single integer on a line by itself, the maximum number of customers Fluttershy can serve.

4 3
10 20 30
5 5 10
2 20
1 30
1 32
3 120

3

3 1
10
10
1 10
1 10
1 10

3

10 3
10 30 60
5 30 30
1 10
2 12
1 15
2 20
2 30
3 90
3 90
3 100
1 105
1 140

6