You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

译自 ROIR 2020 Day1 T2. Превышение скорости ，译者 ShineEternal

超速行驶是一种危险的犯法行为，大大增加了交通事故导致悲惨后果的可能性。不幸的是使用使用雷达和相机控制速度并不能完全解决问题。为了防止这种行为的出现，根据汽车在一段道路上的行驶时间来罚款，可以对超速行为进行限制。

现在有 $n$ 段从 $1\sim n$ 编号的公路。第 $i$ 段公路长 $l_i$ 米，其限速为 $v_i$ 米每秒。超速就要罚款，但是为了体现按劳分配，还要对不同程度的超速设置不同的罚款金额。

具体来说，如果不超速则不收罚款；否则，用 $e$ 表示汽车在这段公路上的最大速度减去限速的值：

• 如果 $0<e\leq a_1$，则惩罚为 $f_1$ 个货币单位。

• 如果 $a_1<e\leq a_2$，则惩罚为 $f_2$ 个货币单位。

• ...

• 如果 $a_{m-2}<e\leq a_{m-1}$，则惩罚为 $f_{m-1}$ 个货币单位。

• 如果 $a_{m-1}<e$，则惩罚为 $f_m$ 个货币单位。

目前，有 $q$ 辆车要经过这 $n$ 段道路，每辆车在 $s_i$ 时间到达 $1$ 号路段，在 $t_i$ 时间离开 $n$ 号路段。

你需要计算每辆车在所有路段中最高被罚款的金额至少是多少。

时间从道路开放起计算，即从 $0$ 开始计算。

输入格式

第一行一个正整数 $n$，表示道路段数。

接下来的两行，每行 $n$ 个数，第一行为 $v_i$，第二行为 $l_i$。

第四行为一个正整数 $m$，表示罚款的 $m$ 种不同范围。

接下来的两行，第一行 $m-1$ 个数，为 $a_i$；第二行 $m$ 个数，为 $f_i$。

第七行为一个正整数 $q$，表示共有 $q$ 辆车。

接下来的 $q$ 行，每行两个整数 $s_i,t_i$。

输出格式

输出共 $q$ 行。

对于每辆车，输出它最少被罚款的金额。

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

提示

对于 $100\%$ 的数据，$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$。