Послушай песню
Фикрет-муравьед освоился в одной из социальных сетей. Но общается он довольно своеобразно. Вместо комплиментов и всего прочего он шлёт своей ненаглядной ехидне Кэйт песни. Они давно знакомы, поэтому, Фикрет виртуозно разбирается в её музыкальных предпочтениях. Для каждой песни известны две характеристики: её продолжительность t_i, и удовольствие x_i, которое Кэйт получит, прослушав песню полностью.
Сейчас у Кэйт есть ровно T единиц свободного времени. Зная список имеющихся у Фикрета песен, посчитайте, какое максимальное удовольствие он может доставить Кэйт. Никакие две и более песни не должны прослушиваться одновременно. Переключение между песнями происходит автоматически и без пауз.
Входные данные
В первой строке задаётся количество имеющихся песен n (0 ≤ n ≤ 100). Каждая из следующих n строк содержит 2 целых числа: t_i (1 ≤ t_i ≤ 1000) и x_i (-1000 ≤ x_i ≤ 1000). Далее задаётся число тестовых случаев Q (1 ≤ Q ≤ 10^5) и каждая из следующих Q строк содержит по одному целому числу T (1 ≤ T ≤ 10^4).
Выходные данные
Для каждого из Q запросов в отдельной строке выведите максимальное удовольствие, которое Кэйт может получить.