Description

To handle peak-hour crowds, the bus company will deploy $k$ buses along a route with $n$ transfer stations (numbered 1 to $n$ west-to-east). Each transfer station $i$ has a priority value $v_i$. The travel time from station $i$ to $i+1$ is $s_i$ (ignoring stop time). The railway arrives at station $i$ at time $t_i$. Bus travel time between stations is always ≥ railway travel time.

You must schedule $k$ buses such that:

1. All passengers arriving at any station $i$ at $t_i$ can board a bus (bus arrival time ≥ $t_i$).
2. For each station $i$, the dissatisfaction is calculated as:
   (waiting time for the first bus) × (priority $v_j$ of the bus's origin station).
   If multiple buses arrive simultaneously, passengers choose the one with the smallest $v_j$.

Minimize the total dissatisfaction across all stations for multiple queries with different $t_i$ and $k$.

Input Format

First line: Integer $n$ (number of stations).
Second line: $n-1$ integers $s_1,...,s_{n-1}$ (travel times).
Third line: $n$ integers $v_1,...,v_n$ (priorities).
Fourth line: Integer $p$ (number of railway schedules).

For each schedule:

• Line 1: $n$ integers $t_1,...,t_n$ (railway arrival times).
• Line 2: Integer $q_i$ (number of queries).
• Line 3: $q_i$ integers $k_1,...,k_{q_i}$ (bus counts to test).

Output Format

For each schedule, output $q_i$ integers—the minimal total dissatisfaction for each $k$.

3
3 4
6 2 1
2
1 3 7
2
1 2
2 3 5
3
1 2 4

12 0
36 4 0

6
2 2 2 2 3
13 12 15 9 3 1
3
5 7 9 11 12 13
4
1 2 4 8
3 4 5 7 8 10
3
2 4 5
1000000 1000001 1000002 1000003 1000004 1000005
2
1 3

52 6 0 0
49 3 0
208 31

Hint

【Data Range】
Constraints:

• $1 \leq n \leq 1000$, $1 \leq p \leq 10$
• $s_i \geq t_{i+1} - t_i \geq 0$
• $1 \leq q_i, k_i \leq 10^6$, $0 \leq v_i, \sum s_i \leq 10^6$, $1 \leq t_i \leq 2 \times 10^6$

Subtasks:
| Subtask | $n$ | $q$ | $k_i$ | $\sum s_i$ | Special | Points | |---------|-----|-----|-------|------------|---------|--------| | 1 | 15 | 1e3 | 1e3 | 15 | None | 5 | | 2 | 15 | 1e6 | 1e6 | 1e6 | None | 5 | | 3 | 100 | 1e6 | 1e6 | 1e6 | None | 15 | | 4 | 1e3 | 1e6 | 1e6 | 1e6 | A | 5 | | 5 | 1e3 | 1e6 | 1e6 | 1e6 | B | 30 | | 6 | 1e3 | 1e3 | 1.1e3 | 1e3 | None | 10 | | 7 | 1e3 | 1e6 | 1e6 | 1e6 | None | 30 |

• Special A: $s_i = t_{i+1} - t_i$
• Special B: $v_i = 1$

【Sample Explanation】
Below are feasible optimal bus scheduling plans for the sample queries. Note that there may be multiple valid optimal solutions.

For the first schedule in Sample 1:

• When $k=1$:
  A bus departs station 1 at time $1$. Operational details:
  | | Station 1 | Station 2 | Station 3 |
  | :-------------------: | :-------: | :-------: | :-------: |
  | Railway Arrival Time | $1$ | $3$ | $7$ |
  | Bus Service 1 Arrival | $1$ | $4$ | $8$ |
  | Boarded Service | Service 1 | Service 1 | Service 1 |
  | Waiting Time | $0$ | $1$ | $1$ |

  Service 1 starts at station 1 ($v_1=6$). Total dissatisfaction:

  $$6 \times 0 + 6 \times 1 + 6 \times 1 = 12$$

• When $k=2$:
  Buses depart station 1 at $t=1$ and station 2 at $t=3$. Operational details:
  | | Station 1 | Station 2 | Station 3 |
  | :-------------------: | :-------: | :-------: | :-------: |
  | Railway Arrival Time | $1$ | $3$ | $7$ |
  | Bus Service 1 Arrival | $1$ | $4$ | $8$ |
  | Bus Service 2 Arrival | — | $3$ | $7$ |
  | Boarded Service | Service 1 | Service 2 | Service 2 |
  | Waiting Time | $0$ | $0$ | $0$ |

  Service 1 starts at station 1 ($v_1=6$), Service 2 at station 2 ($v_2=2$). Total dissatisfaction:

  $$6 \times 0 + 2 \times 0 + 2 \times 0 = 0$$

For the second schedule in Sample 1:

• When $k=1$:
  A bus departs station 1 at $t=2$. Operational details:
  | | Station 1 | Station 2 | Station 3 |
  | :-------------------: | :-------: | :-------: | :-------: |
  | Railway Arrival Time | $2$ | $3$ | $5$ |
  | Bus Service 1 Arrival | $2$ | $5$ | $9$ |
  | Boarded Service | Service 1 | Service 1 | Service 1 |
  | Waiting Time | $0$ | $2$ | $4$ |

  Total dissatisfaction:

  $$6 \times 0 + 6 \times 2 + 6 \times 4 = 36$$

• When $k=2$:
  Buses depart station 1 at $t=2$ and station 2 at $t=3$. Operational details:
  | | Station 1 | Station 2 | Station 3 |
  | :-------------------: | :-------: | :-------: | :-------: |
  | Railway Arrival Time | $2$ | $3$ | $5$ |
  | Bus Service 1 Arrival | $2$ | $5$ | $9$ |
  | Bus Service 2 Arrival | — | $3$ | $7$ |
  | Boarded Service | Service 1 | Service 2 | Service 2 |
  | Waiting Time | $0$ | $0$ | $2$ |

  Total dissatisfaction:

  $$6 \times 0 + 2 \times 0 + 2 \times 2 = 4$$

• When $k=4$:
  Buses depart:

  • Station 1 at $t=-2$ and $t=2$.
  • Station 2 at $t=1$ and $t=3$.
    Operational details:

  	Station 1	Station 2	Station 3
  Railway Arrival Time	$2$	$3$	$5$
  Bus Service 1 Arrival	$-2$	$1$
  Bus Service 2 Arrival	$2$	$5$	$9$
  Bus Service 3 Arrival	-	$1$	$5$
  Bus Service 4 Arrival		$3$	$7$
  Boarded Service	Service 2	Service 4	Service 3
  Waiting Time	$0$

  Services 1/2 start at station 1 ($v_1=6$), Services 3/4 at station 2 ($v_2=2$). Total dissatisfaction:

  $$6 \times 0 + 2 \times 0 + 2 \times 0 = 0$$

  Note: At Station 3, Services 1 and 3 arrive simultaneously at $t=5$. Passengers choose Service 3 (lower $v_j=2$) over Service 1 ($v_j=6$).