Фікрет-мурахоїд освоївся в однієй з соціальних мереж. Але спілкується він досить незвичайно. Замість компліментів та усього іншого він шле своїй любій єхидні Кейт пісні. Вони давно знайомі, тому, Фікрет віртуозно розбирається в її музичних перевагах. Для кожної пісні відомі три характеристики: її тривалість \textbf{t_i}, задоволення \textbf{x_i}, яке Кейт отримає, прослухавши пісню повністю і величина \textbf{y_i}, на яку буде зменшуватися задоволення від пісні при кожному наступному її прослуховуванні. Тобто, якщо на даний момент задоволення від пісні дорівнює \textbf{x}, то при другому прослуховуванні цієї ж пісні (необов'язково підряд) воно буде дорівнювати \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{Q }рядків містить по одному цілому числу \textbf{T} (\textbf{1 }≤ \textbf{T} ≤ \textbf{100}). \OutputFile Для кожного з \textbf{Q} запитів у окремому рядку виведіть максимальне задоволення, яке Кейт може отримати.