19871번 - Превышение скорости 서브태스크다국어

Превышение скорости является опасным нарушением, значительно увеличивающим вероятность трагических последствий транспортных происшествий. К сожалению контроль скорости с использованием радаров и камер не решает проблему полностью. Притормаживая перед камерами, водители едут со значительным превышением на участках дорог, где контроль не ведётся. С целью предотвращения такого поведения используется назначение штрафа за гарантирование превышение скорости, основанное на времени проезда дороги.

Рассмотрим дорогу, состоящую из n участков, пронумерованных от 1 до n. Длина i-го участка составляет l_i метров. На i-м из участков установлено ограничение по скорости в v_i м/с.

За превышение скорости предусмотрены штрафы. В зависимости от превышения, установлены различные штрафы, величина штрафа вычисляется следующим образом.

Пусть e — максимальное превышение разрешённой скорости в процессе пребывания автомобиля на всей дороге, то есть максимальная разница между скоростью автомобиля и максимальной разрешенной скоростью на участке, где он в этот момент находится. Если превышения скорости не было, то штраф не взимается. В противном случае штраф вычисляется так:

• если 0 < e ≤ a₁, то штраф составляет f₁ денежных единиц;
• если a₁ < e ≤ a₂, то штраф составляет f₂ денежных единиц;
• . . .
• если a_m−2 < e ≤ a_m−1, то штраф составляет f_m−1 денежных единиц;
• если a_m−1 < e, то штраф составляет fm денежных единиц.

Таким образом, есть m диапазонов превышения скорости и соответствующие им штрафы.

Автоматическая система назначения штрафов получила данные о q автомобилях. Для удобства пронумеруем их от 1 до q. Известно, что i-й автомобиль заехал на дорогу в момент времени s_i, проехал все n участков, после чего выехал с нее в момент времени t_i. Отсчёт времени будем вести в секундах с открытия дороги.

Для каждого из автомобилей система должна определить, какой максимальный штраф можно гарантированно выписать этому автомобилю, основываясь только на времени заезда на дорогу и выезда с нее.

Требуется написать программу, которая по описанию границ диапазонов превышения скорости, соответствующих штрафов и временам въезда/выезда автомобилей определяет для каждого автомобиля максимальный штраф, который можно выписать этому автомобилю.

Первая строка входных данных содержит единственное целое число n — количество участков на дороге (1 ≤ n ≤ 10).

Вторая строка содержит n целых чисел v_i — ограничения скорости на участках (1 ≤ v_i ≤ 10⁹).

Третья строка содержит n целых чисел l_i — длины участков (1 ≤ l_i ≤ 10⁹).

Четвертая строка содержит единственное целое число m — количество границ диапазонов превышения скорости (1 ≤ m ≤ 10⁵).

Пятая строка содержит m − 1 целых чисел a_i — границы диапазонов превышения скорости (1 ≤ a_i ≤ 10⁹). Гарантируется, что значения a_i строго возрастают. Обратите внимание, что если m = 1, то пятая строка ввода пустая.

Шестая строка содержит m целых чисел f_i — штрафы за диапазоны превышения скоростей (1 ≤ f_i ≤ 10⁹). Гарантируется, что значения f_i возрастают.

Седьмая строка содержит единственное целое число q — количество автомобилей, которые надо обработать (1 ≤ q ≤ 10⁵).

Каждая из следующих q строк содержит два целых числа s_i и t_i — время заезда на трассу и выезда с неё i-го из рассматриваемых автомобилей (1 ≤ s_i < t_i ≤ 10⁹).

Для каждого из q автомобилей выведите в отдельной строке максимальный штраф, который гарантированно можно выписать этому автомобилю, основываясь только на временах его заезда на дорогу и выезда с нее. Если возможна ситуация, что автомобиль ни разу не превысил разрешённую скорость, следует вывести 0.

Гарантируется, что если время въезда или выезда автомобиля изменить не более чем на 10⁻⁵, штраф, который можно ему выписать, не изменится.