Послухай пісню (Hard)#4364

Послухай пісню (Hard)

1 секунда

64 мегабайти

Середня

Фікрет-мурахоїд освоївся в одній із соціальних мереж. Але спілкується він досить незвичайно. Замість компліментів та усього іншого він шле своїй любій єхидні Кейт пісні. Вони давно знайомі, тому, Фікрет віртуозно розбирається в її музичних перевагах. Для кожної пісні відомі три характеристики: її тривалість $t_{i}$ t_i, задоволення $x_{i}$ x_i, яке Кейт отримає, прослухавши пісню повністю і величина $y_{i}$ y_i, на яку буде зменшуватися задоволення від пісні при кожному наступному її прослуховуванні. Тобто, якщо на даний момент задоволення від пісні дорівнює $x$ , то при другому прослуховуванні цієї ж пісні (необов'язково підряд) воно буде дорівнювати $(x - y)$ (x-y), при третьому $(x - y - y)$ (x-y-y) ...

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

Вхідні дані

У першому рядку задається кількість наявних пісень $n$ ( $0 \leq n \leq 100$ 0 \le n \le 100). Кожен з наступних $n$ рядків містить $3$ цілих числа: $t_{i}$ t_i ( $1 \leq t_{i} \leq 100$ 1 \le t_i \le 100), $x_{i}$ x_i ( $- 100 \leq x_{i} \leq 100$ -100 \le x_i \le 100), $y_{i}$ y_i ( $- 100 \leq y_{i} \leq 100$ -100 \le y_i \le 100). Далі задається кількість тестових випадків $Q$ ( $1 \leq Q \leq 1 0^{5}$ 1 \le Q \le 10^5) і кожен з наступних $Q$ рядків містить по одному цілому числу $T$ ( $1 \leq T \leq 100$ 1 \le T \le 100).

Вихідні дані

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

Приклади

Приклад 1