Dinlə mahnını (Hard)#4364
Fikret, bir sosial şəbəkədə özünü çox rahat hiss edən bir qarışqa yeyəndir. Lakin o, ünsiyyəti olduqca qeyri-adi şəkildə qurur. Təriflər və digər şeylər əvəzinə, sevimli kirpisi Keytə mahnılar göndərir. Onlar uzun müddətdir dostdurlar, buna görə də Fikret Keytin musiqi zövqünü mükəmməl bilir. Hər bir mahnı üçün üç xüsusiyyət məlumdur: mahnının müddəti t_i, Keytin mahnını tam dinlədikdən sonra alacağı məmnuniyyət x_i və hər növbəti dinləmədə mahnıdan alınan məmnuniyyətin azalacağı dəyər y_i. Yəni, əgər bu anda mahnıdan alınan məmnuniyyət x-ə bərabərdirsə, bu mahnını ikinci dəfə (mütləq ardıcıl olmaya bilər) dinlədikdə o, (x-y)-ə, üçüncü dəfə isə (x-2y)-ə bərabər olacaq...
Hal-hazırda Keytin dəqiq T vahid boş vaxtı var. Fikretin mövcud mahnılar siyahısını bilə-bilə, Keytə maksimum hansı məmnuniyyəti çatdıra biləcəyini hesablayın. Heç bir iki və ya daha çox mahnı eyni vaxtda dinlənilməməlidir. Mahnılar arasında keçid avtomatik və fasiləsiz baş verir.
Birinci sətirdə mövcud mahnıların sayı n (0 ≤ n ≤ 100) verilir. Növbəti n sətirdən hər biri 3 tam ədəd ehtiva edir: t_i (1 ≤ t_i ≤ 100), x_i (-100 ≤ x_i ≤ 100), y_i (-100 ≤ y_i ≤ 100). Sonra test hallarının sayı Q (1 ≤ Q ≤ 10^5) verilir və növbəti Q sətirdən hər biri bir tam ədəd T (1 ≤ T ≤ 100) ehtiva edir.
Hər bir Q sorğu üçün ayrı-ayrı sətirdə Keytin ala biləcəyi maksimum məmnuniyyəti göstərin.
Nümunə 1