Fast Food Mükafatları#6396
Regional yarışma zamanı, məşhur bir fast food restoranının Kanada filialı, biznesini təşviq etmək üçün bir oyun keçirir. Müəyyən qida məhsulları stikerlər təqdim edir və müxtəlif stiker kolleksiyaları nağd mükafatlara çevrilə bilər. Əgər bir mükafat T_1, T_2, ..., T_k tipli stikerlər tələb edirsə, onda siz hər bir T_1, T_2, ..., T_k tipindən stikerə malik olduğunuz halda mükafatı tələb edə bilərsiniz. Hər bir stiker yalnız bir mükafatı tələb etmək üçün istifadə edilə bilər. Lakin, eyni tipdən bir neçə stikerə malik olduğunuz halda bir mükafatı bir neçə dəfə tələb edə bilərsiniz. Heç iki mükafat eyni tip stikerlər tələb etməyəcək. Bəzi stikerlər nağd mükafat tələb etmək üçün istifadə edilə bilməz (məsələn, pulsuz milkshake üçün stiker).
Regional yarışmaya yol səyahətinizdə, məşqçiniz sizi bu restoranda yeməyə məcbur etdi və bütün stikerləri birlikdə topladı. Məşqçiniz nə qədər nağd mükafat tələb edə bilər?
Giriş bir neçə test halından ibarətdir. Girişin ilk sətri, davam edəcək test hallarının sayını göstərən, -dən çox olmayan tək bir tam ədəddir. Hər bir hal iki tam ədəd (1 \leq n \leq 10) və (1 \leq m \leq 30) ilə başlayır, burada müxtəlif mükafat növlərinin sayını, isə müxtəlif stiker növlərinin sayını göstərir (növlər , , ..., ilə etiketlənmişdir). Növbəti sətir mükafatları göstərir. Bu sətirlərin hər biri, mükafatı tələb etmək üçün tələb olunan stiker növlərinin sayını göstərən (1 \leq k \leq m) tam ədədi ilə başlayır. Bu, tələb olunan stiker növlərini göstərən tam ədədlə davam edir. Hər bir sətirin son tam ədədi mükafatın (müsbət) nağd dəyəridir (ən çox ). Hər bir halın son sətri qeyri-mənfi tam ədəd verir, burada -ci tam ədəd məşqçinizin topladığı tipli stikerlərin sayını göstərir. Hər bir tipdən ən çox stiker var.
Hər bir hal üçün, tələb edilə bilən nağd mükafatların ümumi dəyərini tək bir sətirdə göstərin.
Nümunə 1