smoothie-web Problems Contests Ranking About
Login Register

BSSPC 2019 P5 - Taro Milk Tea

data_usage Points
timer Time Limit
linear_scale Memory Limit

Problem Statement

Amey is a student at Bayview Secondary School and like for any other filthy Bayview student, milk tea is a staple drink. As for Amey, he especially likes potato juice taro milk tea. Being the taro milk tea connoisseur he is, he will only drink milk tea with sugar concentrations ranging from aa to bb.

Around Bayview Secondary, there are nn different milk tea stores which are built beside each other, which each sell taro milk tea with a sugar concentration of cic_i . Additionally, each milk tea store has an effect rating eie_i to indicate the popularity of a milk tea store.

Recently, qq surveys have been conducted by certain milk tea vendors. The results of each survey indicate how much the concentration of sugar should increase by through an integer value. Other milk tea stores within the effect range (all milk tea stores eie_i units to the left and right up until store 1 or store nn. In other words, stores within the range [1ei,i+ei][1 − e_i , i + e_i]) will also follow suit by adding the same amount of sugar in hopes of more customers.

Find the number of milk tea stores that Amey will be willing to buy and drink taro milk tea from after all the surveys and sugar concentration adjustments.

Input Specification

The first line will be the number of milk tea stores near Bayview Secondary, n.

The next line of input will be Amey’s sugar concentration tolerance [a,b][a, b].

The next line will be nn integers, separated by a space, which represent the base sugar concentrations in the milk tea of each store (c1,c2,c3,...,cnc_1 , c_2, c_3 , ..., c_n).

The next line will be nn integers, separated by a space, which represent the effect rating of each milk tea store (e1,e2,e3,...,ene_1, e_2, e_3 , ..., e_n).

The next line contains the number qq, representing the number of surveys conducted by the nearby stores.

Finally, qq lines follow each containing two integers in the form srs r, with ss representing the index of the store which conducted the survey, and rr representing the result of the survey.

Output Specification

Print out the number of milk tea stores that Amey is willing to drink from.


For all subtasks:

1n1051 ≤ n ≤ 10^5.

1ab10121 \le a \le b \le 10^{12}

1ci109,1ein1 \le c_i \le109 , 1 \le ei \le n

1sn,1r1091 \le s \le n, 1 \le r \le 10^9

Subtask 1 [20%]

1q10001 \le q \le 1000

Subtask 2 [80%]

1q1051 \le q \le 10^5

Sample Input

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

Sample Output