Розваги на американських гірках#3778
Джиммі та його друзі обожнюють відвідувати великі тематичні парки. У поточному парку розваг є багато американських гірок, які Джиммі потім класифікує. Він призначає кожній гірці значення веселощів, але з кожним заїздом це значення зменшується.
Більш формально: для конкретної американської гірки , Джиммі призначає два коефіцієнти веселощів a_i та b_i. Під час катання на цій гірці в -й раз, Джиммі отримує значення веселощів f(i, k) = a_i-(k-1)^2 \cdot b_i. Якщо f(i, k) стає непозитивним, катання на гірці більше не приносить задоволення.
Джиммі намагається максимізувати загальні веселощі, поки не залишить парк. Чи можете ви підрахувати, скільки веселощів він може отримати за певний час?
Вхід складається з одного тестового випадку.
Перша строка містить ціле число , де — це кількість різних американських гірок у тематичному парку (0 < N \leq 100).
Наступні рядків містять цілі числа a_i, b_i та t_i, де a_i та b_i є коефіцієнтами веселощів, як зазначено вище, а t_i — це час для одного заїзду на -й гірці (0 \leq a_i \leq 1000; 0 \leq b_i \leq 1000; 0 < t_i \leq 25000).
Наступний рядок містить додатне ціле число , що позначає кількість разів, коли Джиммі відвідує парк (0 \leq Q \leq 1000). Кожен з наступних рядків містить цілий час T_i, який Джиммі проводить під час свого -го візиту (0 \leq T_i \leq 25000).
Для кожного з можливих разів, надрукуйте один рядок, що містить максимальне загальне значення веселощів, якщо Джиммі проводить T_i хвилин у тематичному парку.
Приклад 1