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