Американские горки - это веселье
Джимми и его друзья обожают посещать крупные тематические парки. В текущем парке много американских горок, и Джимми классифицирует их по уровню веселья. Каждой горке он присваивает значение веселья, которое уменьшается с каждым новым заездом.
Более формально: для каждой американской горки 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 минут в тематическом парке.