Minimizing Passenger Dissatisfaction on Bus Commuter Service

Due to the growing urban population, there is an increased pressure on the suburban railway in city H. To cope with a short‐term large passenger flow during the morning peak, the bus group decides to schedule a number of bus services on a certain bus line running in the same eastbound direction as the railway. This facilitates transfers for train passengers who then take the bus to reach their destination.

The bus route consists of n transfer stations numbered 1 through n from west to east. Each station i has an associated importance value v_i that reflects its focus on operational efficiency. The travel time for any bus between station i and i+1 is given by s_i (the same for all buses on that segment), and the dwell time is negligible. The suburban railway reaches station i at time t_i. It is guaranteed that the bus travel time between any two consecutive stations is at least the railway travel time between them.

You are to schedule exactly k bus services. All n stations have passengers disembarking from the railway. For each bus, you can arbitrarily choose its starting transfer station and its departure time. However, the schedules must satisfy the condition that for every station i, the earliest bus that arrives (that is, the bus whose arrival time at station i is the smallest among those arriving no earlier than t_i) has an arrival time not earlier than t_i, ensuring that all waiting passengers are served.

Once a bus departs its chosen starting station, it travels eastbound, stopping at every station along the way to pick up all waiting passengers. Passengers will board the very first bus that arrives at their station after the train’s arrival. The dissatisfaction at station i is defined as:

Dissatisfaction = (waiting time) × (importance of the bus’s starting station),

where the waiting time is the difference between the bus’s arrival time and t_i. In the event that more than one bus arrives simultaneously at a station, the passengers are considered to board the bus whose starting station has the smallest importance value. Your goal is to choose the starting stations and departure times for the k bus services so that the sum of dissatisfaction over all n stations is minimized.

Since the suburban railway timetable and the available number of buses change frequently, you will be given several queries with different t_i values and k values. For each query, report the minimum total dissatisfaction achievable.

---

Input Format

The input begins with an integer n — the number of transfer stations. The next line contains n integers, representing the importance values v₁, v₂, ..., v_n of the stations. The following line contains n-1 integers, where the i^th integer represents the travel time s_i between station i and station i+1.

The next line contains an integer Q, the number of queries. Each query is described in the following line: first an integer k, the number of bus services to schedule, followed by n integers representing the railway arrival times t₁, t₂, ..., t_n at the respective stations.

---

Output Format

For each query, output a single line with one integer — the minimum total dissatisfaction over all n stations.

inputFormat

The first line contains an integer n (the number of transfer stations).

The second line contains n space-separated integers v₁, v₂, ..., v_n.

The third line contains n-1 space-separated integers s₁, s₂, ..., s_n-1.

The fourth line contains an integer Q (the number of queries).

Each of the next Q lines begins with an integer k (the number of bus services) followed by n space-separated integers t₁, t₂, ..., t_n (the railway arrival times).

outputFormat

For each query, output the minimum total dissatisfaction, each on a separate line.

sample

3
1 2 3
1 2
3
1 1 3 6
2 1 3 6
3 1 3 6

3
2
0

</p>