Задача 2. Превышение скорости

Автор:Центральная предметно-методическая комиссия   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

Формат входных данных

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

Вторая строка содержит n целых чисел vi — ограничения скорости на участках.

Третья строка содержит n целых чисел li — длины участков.

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

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

Шестая строка содержит m целых чисел fi — штрафы за диапазоны превышения скоростей. Гарантируется, что значения fi возрастают.

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

Каждая из следующих q строк содержит два целых числа si и ti — время заезда на трассу и выезда с неё i-го из рассматриваемых автомобилей .

Формат выходных данных

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

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

Ограничения

1 ≤ n ≤ 10

1 ≤ vi, li, ai, fi ≤ 109

1 ≤ m, q ≤ 105

1 ≤ si < ti ≤ 109

Система оценивания

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

Подзадача Баллы Ограничения Необходимые подзадачи Информация о проверке
15 n = 1, m = 1 первая ошибка
210m = 1 1 первая ошибка
39 n = 1, m ≤ 10 1 первая ошибка
412n = 1 1, 3 первая ошибка
513m ≤ 10, ai ≤ 10 первая ошибка
614m ≤ 10 1, 2, 3, 5первая ошибка
737 1 — 6 первая ошибка

Примеры тестов

Стандартный вход Стандартный выход
1
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

0.068s 0.010s 13