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