Speeding Fines

This problem is adapted from ROIR 2020 Day1 T2 (Превышение скорости), translated by ShineEternal.

A driver traveling through a highway composed of n segments may choose different speeds on each segment in order to meet a prescribed total travel time. The highway is divided into segments numbered from 1 to n. In the i-th segment, the length is l_i meters and the speed limit is v_i meters per second. If a driver does not exceed the speed limit, no fine is incurred. Otherwise, let $$ e = \text{(maximum speed on the segment)} - v_i. $$ The fine for that segment is determined by the thresholds given below:

• If \(0 < e \le a_1\), the fine is \(f_1\) monetary units.
• If \(a_1 < e \le a_2\), the fine is \(f_2\) monetary units.
• \(\vdots\)
• If \(a_{m-2} < e \le a_{m-1}\), the fine is \(f_{m-1}\) monetary units.
• If \(a_{m-1} < e\), the fine is \(f_m\) monetary units.

There are q vehicles. For each vehicle, you are given the time \(s_i\) when it enters segment 1 and \(t_i\) when it leaves segment n. The driver is allowed to choose a speed for each segment subject to the constraint that the overall travel time (the sum of times on all segments) does not exceed \(T = t_i - s_i\).

The twist is that the driver can adjust the speed on each segment up to a certain maximum allowed speed if willing to pay a higher fine. In particular, if the driver restricts the maximum fine incurred on any segment to at most \(F\), then on each segment the speed must not exceed a value determined as follows:

• If \(F < f_1\), then the driver cannot exceed the speed limit, i.e. the maximum speed is \(v_i\).
• If \(f_1 \le F < f_2\), then the driver may drive at up to \(v_i + a_1\).
• If \(f_2 \le F < f_3\), then up to \(v_i + a_2\).
• \(\vdots\)
• If \(f_{m-1} \le F < f_m\), then up to \(v_i + a_{m-1}\).
• If \(F \ge f_m\), the driver is allowed to drive arbitrarily fast (i.e. no effective speed bound).

Your task is: for each vehicle, compute the minimum possible value of the maximum fine that must be incurred on at least one segment in order to complete the journey within the allotted time.

Input Format

The input is given as follows:

n m
l1 v1
...
ln vn
a1 a2 ... am-1
f1 f2 ... fm
q
s1 t1
...
sq tq

Here, the first line contains two integers n and m. Each of the following n lines contains two integers: the length \(l_i\) and the speed limit \(v_i\) for segment i. The next line contains \(m-1\) integers representing the thresholds \(a_1, a_2, \ldots, a_{m-1}\). The following line contains \(m\) integers representing the fines \(f_1, f_2, \ldots, f_m\> in order. Finally, the next line contains an integer q, followed by q lines each containing two integers \(s_i\) and \(t_i\) for a vehicle.

Output Format

For each vehicle, output a single integer: the minimum possible maximum fine required across all segments to finish the journey in time.

Explanation

Let the base travel time of the highway be \(T_0 = \sum_{i=1}^{n} \frac{l_i}{v_i}\) (i.e. traveling without speeding). A vehicle with available time \(T = t_i - s_i\) can complete the journey without any fine if \(T \ge T_0\), and in that case the answer is 0. Otherwise, define for each allowable fine level (except 0) the corresponding maximum speed on segment i as follows:

• If the maximum fine allowed is in \([f_1, f_2)\), the maximum speed is \(v_i + a_1\), and the minimum travel time on segment i becomes \(\frac{l_i}{v_i+a_1}\). Similarly, if the maximum fine allowed is in \([f_j, f_{j+1})\), the maximum speed is \(v_i + a_j\). Finally, if \(F \ge f_m\), the speed is unbounded and the travel time can be made arbitrarily small.

Find the smallest fine \(F\) (which will be one of \(f_1, f_2, \ldots, f_m\)) such that the sum of the minimum travel times over all segments is at most \(T\).

inputFormat

// First line: two integers n and m
n m
// Next n lines: each contains two integers l_i and v_i
l1 v1
l2 v2
...
ln vn
// Next line: m-1 integers a1, a2, ..., a_(m-1)
a1 a2 ... a_(m-1)
// Next line: m integers f1, f2, ..., fm
f1 f2 ... fm
// Next line: an integer q, the number of vehicles
q
// Then q lines, each with two integers s_i and t_i
s1 t1
s2 t2
...
sq tq

</p>

outputFormat

For each of the q vehicles, output a single integer in one line – the minimum possible maximum fine (in monetary units) that must be incurred on at least one segment to complete the journey in the allotted time.

sample

1 3
100 10
5 10
100 200 300
3
0 11
0 8
0 4

0
100
300

</p>