Задача D. Новые особенности
Задачу добавил: alef
Успешно сдано решений: 318
Будущий программист Кеша незадолго до стажировки изучил ряд нововведений в том языке, на котором он пишет. И, конечно, он хочет применить эти знания на практике.
Кеше предстоит разработать 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