Dinlə mahnını#4363
Fikret, bir sosial şəbəkədə özünü rahat hiss edən bir qarışqa yeyəndir. Lakin o, ünsiyyəti olduqca qeyri-adi bir şə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 tanışdırlar, buna görə də Fikret onun musiqi zövqlərini mükəmməl bilir. Hər bir mahnı üçün iki xüsusiyyət məlumdur: onun müddəti t_i və Keytin mahnını tam dinlədikdən sonra alacağı məmnuniyyət x_i.
Hazırda Keytin dəqiq T vahid boş vaxtı var. Fikretin mövcud mahnılar siyahısını bilə-bilə, Keytə hansı maksimum 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ətirin hər biri 2 tam ədəd ehtiva edir: t_i (1 ≤ t_i ≤ 1000) və x_i (-1000 ≤ x_i ≤ 1000). Daha sonra test hallarının sayı Q (1 ≤ Q ≤ 10^5) verilir və növbəti Q sətirin hər biri bir tam ədəd T (1 ≤ T ≤ 10^4) ehtiva edir.
Hər bir Q sorğusu üçün ayrıca sətirdə Keytin ala biləcəyi maksimum məmnuniyyəti göstərin.
Nümunə 1