Послухай пісню (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 запитів у окремому рядку виведіть максимальне задоволення, яке Кейт може отримати.