eolymp
bolt
Try our new interface for solving problems
Məsələlər

Послушай песню (Hard)

Послушай песню (Hard)

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Фикрет-муравьед освоился в одной из социальных сетей. Но общается он довольно своеобразно. Вместо комплиментов и всего прочего он шлёт своей ненаглядной ехидне Кэйт песни. Они давно знакомы, поэтому, Фикрет виртуозно разбирается в её музыкальных предпочтениях. Для каждой песни известны три характеристики: её продолжительность t_i, удовольствие x_i, которое Кэйт получит, прослушав песню полностью и величина y_i, на которую будет уменьшаться удовольствие от песни при каждом следующем её прослушивании. То есть, если на данный момент удовольствие от песни равно x,то при втором прослушивании этой же песни (необязательно подряд) оно будет равно (x-y), при третьем (x-y-y)...

Сейчас у Кэйт есть ровно T единиц свободного времени. Зная список имеющихся у Фикрета песен, посчитайте, какое максимальное удовольствие он может доставить Кэйт. Никакие две и более песни не должны прослушиваться одновременно. Переключение между песнями происходит автоматически и без пауз.

Giriş verilənləri

В первой строке задаётся количество имеющихся песен n (0 n100). Каждая из следующих n строк содержит 3 целых числа: t_i (1 t_i100), x_i (-100 x_i100), y_i (-100 y_i100). Далее задаётся число тестовых случаев Q (1 Q10^5)и каждая из следующих Q строк содержит по одному целому числу T (1 T100).

Çıxış verilənləri

Для каждого из Q запросов в отдельной строке выведите максимальное удовольствие, которое Кэйт может получить.

Nümunə

Giriş verilənləri #1
2
2 1 1
3 5 0
2
4
5
Çıxış verilənləri #1
5
6
Müəllif Борис Соколов
Mənbə Дистанционная Летняя Компьютерная Школа - лето 2013 года