+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! ولی از آن‌جایی که حیدری خیلی ذوق تولدش را دارد تا الان $T$ مهمانی تولد گرفته و در هرکدام تعدادی کادو از دوستانش دریافت کرده است. حیدری بعد از هر مهمانی ‌کادوهایش را به ترتیب باز می‌کند، و بعد از باز کردن هر کادو به اندازه مجموع ارزش کادوهایی که تا به الان باز کرده خوش‌حالی می‌کند. برای مثال اگر او ۲ کادو به ارزش ۲ تومان و ۷ تومان هدیه بگیرد پس از باز کردن اولی ۲ بار خوش‌حالی می‌کند، و پس از باز کردن دومی ۲ + ۷ = ۹ بار خوش‌حالی می‌کند. این به این معناست که در آخر شب او مجموعاً ۲ + ۹ = ۱۱ بار خوش‌حالی کرده است. می‌دانیم همه دوستان حیدری کادوهایشان را از مغازه علی‌آقا می‌خرند و اجناس مغازه علی‌آقا $M$ قیمت متفاوت دارد. حال حیدری به ازای هر مهمانی تولد به شما قیمت اجناس مغازه علی‌آقا و هم‌چنین عدد $N$ مجموع خوش‌حالی‌هایی را که آن شب کرده است می‌گوید، شما بیش‌ترین مجموع قیمت ممکن برای کادو‌هایی که حیدری دریافت کرده است را بگویید! # ورودی در خط اول ورودی $T$ تعداد مهمانی‌های حیدری داده شده است. برای هر مهمانی به ترتیب دو عدد $N$ مجموع خوش‌حالی‌های حیدری در آن شب و $M$ تعداد قیمت‌های متفاوت اجناس مغازه علی‌آقا در یک خط داده می‌شود. سپس در خط بعدی $M$ عدد متفاوت آمده است که نشان دهنده قیمت اجناس مغازه علی‌آقاست. می‌دانیم قیمت اجناس مغازه حداقل ۱ و حداکثر ۲۰ تومان است. $$1 \le T \le 20$$ $$1 \le N \le 5000$$ $$1 \le M \le 10$$ # خروجی در $T$ خط خروجی برای هر مهمانی، بیش‌ترین مجموع ارزش ممکن کادو‌هایی که حیدری گرفته است را چاپ کنید و اگر ممکن نیست همه اجناس از مغازه علی‌آقا خریداری شده باشد و حیدری دقیقاً $N$ بار خوش‌حالی کرده باشد عدد `-1` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 29 3 7 3 2 15 1 1 16 1 1 6 2 3 1 ``` ## خروجی نمونه ۱ ``` 14 5 -1 3 ```