Условие:
В игре используется своя валюта — тугрики. Игрок начинает с пустыми карманами, то есть с нулём тугриков. Процесс делится на игровые дни. В каждый день можно выполнить одно из двух действий:
Пойти на работу самому. За это в конце рабочего дня выдаётся зарплата — 1 тугрик.
Купить предприятие на территории Берляндии. Всего есть N видов предприятий. Предприятие с видом i стоит Ai тугриков и производит Bi тугриков в день, начиная со следующего дня после покупки.
Количество доступных предприятий каждого типа неограниченно. Ход устроен следующим образом: сначала мы идём на работу или совершаем покупку, после чего получаем прибыль за все предприятия, купленные до этого хода.
Валя хочет провести Q соревнований. В соревновании номер j игрокам будет дано Tj игровых дней, чтобы заработать как можно больше тугриков. Для каждого соревнования скажите, какое наибольшее количество тугриков может быть на счёте игрока к концу данного периода?
Исходные данные
В первой строке дано целое число N — количество доступных типов предприятий (1 ≤ N ≤ 100).
Далее идёт N строк, в i-й из них по два целых числа Ai и Bi — стоимость покупки i-го предприятия и заработок с него в игровой день (1 ≤ Ai, Bi ≤ 100).
В следующей строке дано число Q — количество соревнований (1 ≤ Q ≤ 50 000).
Далее идёт Q строк, в j-й из них дано целое число Tj — длительность соревнования в игровых днях (1 ≤ Tj ≤ 100000000).
Выведите Q строк, в j-й из них единственное целое число — наибольшее возможное количество тугриков к концу Tj-го дня.
