A. Сумасшедшие транспортные налоги
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Артур Флек ведь когда-то был обычным человеком с обычными потребностями. Одной из них была покупка автомобиля.

Как известно, владение автомобилем подразумевает уплату транспортного налога, и Готэм в этом отношении не является исключением. Чтобы узнать стоимость транспортного налога на автомобиль, нужно знать мощность его двигателя в лошадиных силах. Далее по таблице налоговых ставок нужно выяснить налоговую ставку на данную мощность, а затем полученная ставка умножается на мощность.

Пример таблицы налоговых ставок:

Мощность (л.с.)Ставка
024
10035
15050
20075
250150

Ставка, записанная в $$$i$$$-й строке, применяется для численных значений мощностей, которые строго больше мощности, указанной в той же строке, но при этом меньше либо равны мощности, указанной в следующей строке (если такая есть). В случае, если мощность строго больше максимальной мощности, указанной в таблице, то применяется максимальная ставка.

В процессе выбора автомобиля Артур перебрал множество вариантов и для каждого из них он хочет знать величину транспортного налога. Помогите ему!

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

В первой строке дано целое число $$$n$$$ — число строк в таблице налоговых ставок ($$$1 \le n \le 100\,000$$$).

В следующих $$$n$$$ строках даны пары чисел $$$b_i$$$, $$$t_i$$$ — мощность и соответствующая диапазону налоговая ставка из $$$i$$$-й строки ($$$0 \le b_i, t_i \le 10^9$$$). Гарантируется, что $$$b_1 = 0$$$, а также для любого $$$i$$$ верно: $$$b_i \lt b_{i + 1}$$$ и $$$t_i \le t_{i+1}$$$.

В следующей строке дано число $$$m$$$ — число автомобилей, транспортный налог на которые хочет узнать Артур ($$$1 \le m \le 100\,000$$$).

В $$$j$$$-й из следующих $$$m$$$ строк дано целое число $$$q_j$$$ — мощность $$$j$$$-го автомобиля ($$$1 \le q_j \le 10^9$$$).

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

Для каждого варианта автомобиля, интересующего Артура, выведите величину транспортного налога на него.

Пример
Входные данные
5
0 24
100 35
150 50
200 75
250 150
5
107
143
152
170
150
Выходные данные
3745
5005
7600
8500
5250