- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
باقر سرما خورده و مقادیر زیادی خسته است.
باقر $n$ کاشی مربعی دارد که طول ضلع $i$اُمین کاشی عددی صحیح و برابر $a_i$ است. باقر میخواهد مجموع مساحت این کاشیها دقیقا برابر $m$ شود. برای دستیابی به این هدف او میتواند در هر مرحله یک کاشی به ضلع $a$ را به یک کاشی به ضلع $b$ تبدیل کند، که عدد $b$ عددی صحیح و نامنفی است و میتواند کمتر یا بیشتر از عدد $a$ باشد، ولی چون خودش خسته است، این کار را به کاشیکار میسپارد و $(a-b)^2$ ریال برای انجام این کار به کاشیکار میپردازد (دقت کنید که طول و عرض هر کاشی همیشه یکسان خواهد بود).
به دلیل اینکه تغییر متعدد طول ضلع یک کاشی مقاوت کاشی را کم میکند، طول ضلع هر کاشی را حداکثر یک بار میتوان تغییر داد.
شما برای باقر کمترین میزان پولی که باید به کاشیکار بپردازد تا مجموع مساحت کاشیها دقیقا برابر $m$ شود را به دست آورید.
ورودی
در خط اول $n$ و $m$ داده شده است.
در خط دوم تا خط $n+1$ام در هر خط طول ضلع یکی از کاشیها داده شده است. $$1 \le n \le 10$$ $$1 \le m \le 10\ 000$$ $$1 \le a_i \le 100$$ تمامی اعداد ورودی عددی صحیح هستند.
خروجی
در تنها خط خروجی کمترین میزان پولی که باقر باید به کاشیکار بپردازد تا مجموع مساحت کاشیها برابر $m$ شود را چاپ کنید.
درصورتی که رسیدن به مجموع مساحت $m$ غیر ممکن بود، عدد -1
را در خروجی چاپ کنید.
مثال
ورودی نمونه
3 6
3
3
1
خروجی نمونه
5
باقر با پرداخت ۴ ریال یکی از کاشیهای به طول ۳ را به طول ۱ تبدیل میکند و با پرداخت ۱ ریال کاشی به طول ۳ دیگر را به طول ۲ تبدیل میکند.
ارسال پاسخ برای این سؤال