المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۴:سوال ۲۸

عیدی

عمو آیدین امسال احساس کرده بود که خیلی بزرگ شده و بایستی به بچه‌های فامیل عیدی بده! اما چقدر مشکل سر را این دوست گرامی سبز شده: بعد از این‌که خبر توی فامیل پیچید و مثل توپ صدا کرد، هر کدوم از بچه‌ها یک نوع اسکناس رو مشخص کرده که باید عیدی که می‌گیره فقط شامل اون‌قدر تومانی باشه. یه مشکل دیگه هم اینه که وقتی به اولین بچه عیدی داده می‌شه، بقیه بچه‌ها می‌بینند و الباقی به کم‌تر از اون مقدار راضی نمی‌شن. اما چون بچه‌ها حساب و کتاب سرشون نمی‌شه، واسشون هزارتومانی و ده تومانی فقط تفاوت رنگ داره. خلاصه این‌که مقدار پول رو با تعداد اسکناس قاطی کردند!

چون ایشون بسیار سخاوت‌مند هستند دوست دارند از بودجه‌ای که به این کار اختصاص دادند، بیش‌ترین میزانش صرف بشه.

ورودی

در سطر اول فایل ورودی، $n$ تعداد بچه‌ها و $c$ بودجه‌ی اختصاص یافته‌ی عمو به این امر مهم داده شده.

در سطر بعدی به ترتیب عیدی گرفتن نوع اسکناس درخواستی کوچولوها آمده.

خروجی

در تنها سطر خروجی یک عدد بنویسید که حداکثر بودجه‌ای که وی می‌تونه صرف کنه و البته کسی سر و صدا نکنه!

توجه

می‌دانیم که $1\leq n \leq 120$ و $0 \leq c \leq 65000$ قرار دارد. هر یک از اسکناس‌های درخواستی در بازه‌ی $[1...200]$ قرار داره. همه‌ی اعداد ورودی صحیح هستند.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
4 17
3 4 5 7
16

ابزار صفحه