+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! ولی از آن‌جایی که حیدری خیلی ذوق تولدش را دارد تا الان $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 ``` ---------- <details class="orange"> <summary> راهنمایی ۱ </summary> به کمک برنامه‌نویسی پویا جواب سوال را پیدا می‌کنیم. `dp[i][j]` را تعریف می‌کنیم: آیا می‌توان $i$ بار خوش‌حالی کرد و جمع ارزش کادو‌های دریافتی مجموعاً $j$ باشد یا خیر. مقدار این حالت `dp` برابر ۱ است اگر بتوان و در غیر این صورت برابر ۰ است. با کمی دقت می‌توان دیپی را آپدیت کرد. این موضوع در راهنمایی بعدی بیشتر توضیح داده خواهد شد. </details> <details class="orange"> <summary> راهنمایی ۲ </summary> آپدیت دی‌پی به این صورت انجام می‌گیرد که تعیین می‌کنیم کادوی آخری که باز می‌شود از کدام نوع است. به طور مثال می‌توان دی‌پی را به روش بازگشتی شبه‌کد زیر به‌روز کرد! ```c bool update(int tot, int score) { if tot < score: return False if visited[tot][score]: return dp[tot][score] for i in 1 -> M: if score >= price[i]: if update(tot - score, score - a[i]): dp[tot][score] = True visited[tot][score] = True return dp[tot][score] } ``` </details>

حل سؤال در بانک سؤالات