Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача D. Новые особенности

Задачу добавил: alef

Успешно сдано решений: 259

Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт

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

Кеше предстоит разработать n функций, и для каждой функции #j Кеша может сказать, сколько времени wj он потратит, если будет писать функцию, используя нововведения, и сколько времени dj он потратит, если будет писать функцию «привычным образом».

Кеша ещё не вполне уверенно владеет изученными нововведениями, поэтому допускает, что часть функций он напишет без их использования. Он хочет выбрать некоторое значение t, и если для некоторой функции #j значение wj окажется больше, чем t, Кеша будет писать эту функцию привычным образом.

Ваша задача — определить для данных значений t, сколько времени потребуется Кеше, чтобы написать все n функций.

Входные данные

В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество функций.

Во второй строке содержится n целых чисел w1, w2, ..., wn (1 ≤ wj ≤ 106,  j = 1, 2, ..., n), wj — время, которое потребуется Кеше, чтобы написать функцию #j с использованием нововведений.

В третьей строке содержится n целых чисел d1, d2, ..., dn (1 ≤ dj ≤ 106,  j = 1, 2, ..., n), dj — время, которое потребуется Кеше, чтобы написать функцию #j без использования нововведений.

В четвёртой строке содержится целое число q (1 ≤ q ≤ 105) — количество запросов.

В пятой строке содержится q целых чисел t1, t2, ..., tq (1 ≤ tk ≤ 106,  k = 1, 2, ..., q), tk — максимально возможное время, которое Кеша готов потратить на написание функции с использованием нововведений.

Выходные данные

Выведите q строк. В строке #k должен содержаться ответ на соответствующий запрос: сколько времени Кеша потратит на написание всех функций, если на написание одной функции с использованием нововведений он готов потратить не более tk времени.

Система оценки

Подзадача 1 (до 30 баллов)

1 ≤ n,  q ≤ 1000.

Баллы начисляются за каждый пройденный тест.

Подзадача 2 (до 70 баллов)

1 ≤ n,  q ≤ 100000.

Баллы начисляются в случае прохождения всех тестов подзадачи.

По запросу сообщается результат проверки на каждом тесте.

Пример

Входные данные
7
5 11 27 14 8 19 11
8 10 12 20 3 17 7
6
13 3 20 3 10 35
Выходные данные
84
77
80
77
79
95

Сдать задачу

Задать вопрос жюри по этой задаче