Altlayihələr

Rəmzi Sapnaex Həll Edilməmiş İdeyalar (Hİ) adlandırılan yeni şəhərətrafı xidmət kompaniyası yaratdı. Hələlik Rəmzi Hİ-yə işçi qəbul etməmişdi, o öz kompaniyasını hələ genişləndirə bilmirdi, ona görə də ilk bir neçə ayda özü işləməli idi. Bir müddət əvvəl o nazirliklərdən bəzi layihələr almışdı və bütün layihələri müxtəlif qiymətli asılı olmayan kiçik alt layihələrə böldü.

Biz fərz edirik ki, bütün alt layihələr vahid zamanda icra edilir. Məhdud vaxta malik olan Rəmzi gələcəyə optimist baxdığından, digərlərini kənara qoyaraq daha qiymətli alt layihələri qəbul edib ən yaxşı halda nə qədər qazana biləcəyini öyrənmək istəyir.

Giriş verilənləri

Birinci sətirdə bir tam ədəd — test hallarının sayı verilir. Sonra hər test halı üçün bir sətirdə yerləşən məlumatlar gəlir. Hər test halı iki tam ədədlə başlayır: Rəmzinin sərəncamında olan vaxt $t$ və alt layihələrin sayı $p(0\le t,p\le 1000)$. Bu iki ədəddən sonra alt layihələrin qiymətləri olan, mənfi olmayan tam $p_i$ ədədləri gəlir ($0$-dan $32767$-dək, hər iki ədəd də daxil olmaqla).Test hallarındakı bütün ədədlər boşluq işarəsi ilə ayrılırlar.

Çıxış verilənləri

Hər test halı üçün ayrıca sətirdə bir tam ədəd — Rəmziyə əlverişli olan vaxt ərzində qazanmaq mümkün olan maksimum pulun cəmi məbləği (qiymətlərin cəmi) verilir.

Nümunələr