Roller coaster əyləncəsi#3778
Jimmy və dostları böyük əyləncə parklarını ziyarət etməyi sevirlər. Cari əyləncə parkında bir çox roller coaster var və Jimmy onları kateqoriyalara ayırır. O, hər coasterə bir əyləncə dəyəri təyin edir; lakin hər sürüşlə əyləncə azalır.
Daha rəsmi: müəyyən bir roller coaster i üçün Jimmy iki əyləncə əmsalı a_i və b_i təyin edir. Bu roller coasterdə k-cı dəfə sürüşərkən, Jimmy f(i, k) = a_i-(k-1)^2·b_i əyləncə dəyəri qazanır. Əgər f(i, k) müsbət deyilsə, roller coasterdə sürüşmək artıq əyləncəli deyil.
Jimmy parkı tərk edənə qədər ümumi əyləncəni maksimuma çatdırmağa çalışır. Jimmy-ə müəyyən bir vaxt üçün nə qədər əyləncə qazana biləcəyini deyə bilərsinizmi?
Giriş bir test halından ibarətdir.
Birinci sətir əyləncə parkında fərqli roller coasterlərin sayı olan N tam ədədini ehtiva edir (0 < N≤ 100).
Sonrakı N sətir hər biri i-ci roller coaster üçün əyləncə əmsalları olan a_i, b_i və bir sürüş üçün vaxt olan t_i tam ədədlərini ehtiva edir (0 ≤ a_i ≤ 1000; 0 ≤ b_i ≤ 1000; 0 < t_i ≤ 25000).
Növbəti sətir Jimmy-nin parkı ziyarət etdiyi vaxtların sayını göstərən müsbət tam ədəd Q ehtiva edir (0 ≤ Q ≤ 1000). Sonrakı Q sətirin hər biri Jimmy-nin i-ci ziyarəti zamanı sərf etdiyi vaxtı göstərən tam vaxt T_i ehtiva edir (0 ≤ T_i ≤ 25000).
Hər bir Q mümkün vaxt üçün, Jimmy-nin əyləncə parkında T_i dəqiqə sərf etdiyi təqdirdə maksimal ümumi əyləncə dəyərini ehtiva edən bir sətir çap edin.
Nümunə 1