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