Чтобы отвлечься от сложных олимпиадных задач, Валя запускает мобильную игру «Симулятор магната». Цели игры как таковой нет, да и игровой процесс не заканчивается. Всё, что в этой игре надо делать — зарабатывать больше и больше денег. Недавно Валя узнал, что у игры есть сообщество, где люди ставят рекорды по заработанным суммам денег. Его заинтересовал вопрос — сколько денег можно получить за фиксированное время?

Действие игры происходит в Берляндии. В игре используется своя валюта — тугрики. Игрок начинает с пустыми карманами, то есть с нулём тугриков. Процесс делится на игровые дни. В каждый день можно выполнить одно из двух действий:

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

Валя хочет провести Q соревнований. В соревновании номер j игрокам будет дано T_j игровых дней, чтобы заработать как можно больше тугриков. Для каждого соревнования скажите, какое наибольшее количество тугриков может быть на счёте игрока к концу данного периода?

В первой строке дано целое число N — количество доступных типов предприятий (1 ≤ N ≤ 100).

Далее идёт N строк, в i-й из них по два целых числа A_i и B_i — стоимость покупки i-го предприятия и заработок с него в игровой день (1 ≤ A_i, B_i ≤ 100).

В следующей строке дано целое число Q — количество соревнований (1 ≤ Q ≤ 50 000).

Далее идёт Q строк, в j-й из них дано целое число T_j — длительность соревнования в игровых днях (1 ≤ T_j ≤ 10⁸).

Выведите Q строк, в j-й из них единственное целое число — наибольшее возможное количество тугриков к концу T_j-го дня.