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