Description

Translated from ROIR 2020 Day1 T2. Превышение скорости, translated by ShineEternal.

Speeding is a dangerous illegal behavior that greatly increases the chance that traffic accidents lead to tragic consequences. Unfortunately, controlling speed using radar and cameras cannot completely solve the problem. To prevent this behavior, one can limit speeding by imposing fines based on the time a car spends on a section of road.

Now there are $n$ road segments numbered from $1$ to $n$. Segment $i$ has length $l_i$ meters, and its speed limit is $v_i$ meters per second. Speeding will be fined, but to reflect “pay according to work”, different levels of speeding have different fine amounts.

Specifically, if the car does not speed, then there is no fine. Otherwise, let $e$ be the value of the car’s maximum speed on this segment minus the speed limit:

• If $0<e\leq a_1$, the penalty is $f_1$ units of currency.
• If $a_1<e\leq a_2$, the penalty is $f_2$ units of currency.
• ...
• If $a_{m-2}<e\leq a_{m-1}$, the penalty is $f_{m-1}$ units of currency.
• If $a_{m-1}<e$, the penalty is $f_m$ units of currency.

Currently, there are $q$ cars that will pass through these $n$ road segments. Each car arrives at segment $1$ at time $s_i$, and leaves segment $n$ at time $t_i$.

You need to compute, for each car, the minimum possible value of the highest fine amount it is charged among all segments.

Time is measured starting from when the road opens, i.e. starting from $0$.

Input Format

The first line contains a positive integer $n$, the number of road segments.

The next two lines each contain $n$ numbers: the first line is $v_i$, and the second line is $l_i$.

The fourth line contains a positive integer $m$, the number of the $m$ different fine ranges.

The next two lines: the first line contains $m-1$ numbers, which are $a_i$; the second line contains $m$ numbers, which are $f_i$.

The seventh line contains a positive integer $q$, the number of cars.

The next $q$ lines each contain two integers $s_i,t_i$.

Output Format

Output $q$ lines in total.

For each car, output the minimum fine amount it must be charged.

3
10 20 30
400 500 600
6
1 5 10 12 16
100 300 600 800 1000 1500
3
10 100
20 70
45 100

0
800
600

Hint

For $100\%$ of the testdata, $1\leq n\leq 10$, $1\leq v_i,l_i,a_i,f_i\leq 10^9$, $1\leq m\leq 10^5$, $1\le q\le 10^5$, $1\leq s_i<t_i\leq 10^9$.

Translated by ChatGPT 5