Сумасшедшие транспортные налоги

시간 제한2초메모리 제한1024 MB

요약

정렬된 세율 표가 주어질 때, 각 자동차의 엔진 출력에 해당하는 세율을 찾아 세금(세율 곱하기 출력)을 계산한다.

난이도: 보통10점 중 4점
유형: 이분 탐색, 배열, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

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

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

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


Мощность (л.с.)	Ставка
0	24
100	35
150	50
200	75
250	150

Ставка, записанная в $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 < 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$ ).

출력

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

예제1

예제 1

입력

예상 출력