BSSPC 2019 P5 - Taro Milk Tea

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 $a$ to $b$ .

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

Recently, $q$ 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 $e_i$ units to the left and right up until store 1 or store $n$ . In other words, stores within the range $[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]$ .

The next line will be $n$ integers, separated by a space, which represent the base sugar concentrations in the milk tea of each store ( $c_1 , c_2, c_3 , ..., c_n$ ).

The next line will be $n$ integers, separated by a space, which represent the effect rating of each milk tea store ( $e_1, e_2, e_3 , ..., e_n$ ).

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

Finally, $q$ lines follow each containing two integers in the form $s r$ , with $s$ representing the index of the store which conducted the survey, and $r$ representing the result of the survey.

Output Specification

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

Subtasks

For all subtasks:

$1 ≤ n ≤ 10^5$ .

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

$1 \le c_i \le109 , 1 \le ei \le n$

$1 \le s \le n, 1 \le r \le 10^9$

Subtask 1 [20%]

$1 \le q \le 1000$

Subtask 2 [80%]

$1 \le q \le 10^5$

Sample Input