- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
می‌دانیم شرکت پالایش و پخش نخود جایگاه ویژه‌ای در بین اهالی برره دارد.
در راستای این هدف، شرکت پالایش و پخش نخود سالار (با مسؤلیت محدود) در نظر دارد سال آینده نخود مورد نیاز اهالی برره را تأمین کند. در راستای این هدف کَیانوش لیستی از میزان نخود مورد نیاز هر خانوار برره را جمع‌آوری کرده است. طبق برآورد در برره $n$ خانواده زندگی می‌کنند که $i$اُمین آنها در سال آینده به $a_i$ کیلو نخود نیاز خواهد داشت.
شرکت سالار با مذاکرات انجام شده $m$ کیلو نخود به برره وارد کرده است. می‌دانیم هر خانواری که کمتر از نیازش نخود دریافت کند به اندازه‌ی مجذور اختلاف میزان دریافتی با میزان درخواستی‌اش ناسزا نثار سالارخان می‌کند. در صورتی که سالارخان نخودها را به صورت بهینه بین خانوارها پخش کند کمترین تعداد ناسزایی که می‌شنود را به دست آورید (دقت کنید که سالارخان تنها می‌تواند مقادیر صحیح و نامنفی کیلو نخود به هرخانوار بدهد).
ورودی
در خط اول $m$، مقدار نخودی که سالارخان دارد، و $n$، تعداد خانوارهای برره، آمده است. در خط بعدی به ترتیب مقدار نخود مصرفی هر خانوار آمده است. تضمین می‌شود مقدار نخود وارد شده توسط شرکت سالار همیشه کمتر از مجموع نخود مصرفی کل خانوار های برره است. $$1 \le m, a_i \le 2 \times 10^9$$ $$1 \le n \le 100\ 000$$
خروجی
کمترین ناسزایی که در حالت بهینه نثار سالارخان می‌شود را چاپ کنید.
تضمین می شود که جواب مسئله هیچ‌گاه از $4 \times 10^{18} $ بیشتر نمی‌شود.
مثال
ورودی نمونه ۱
5 3
1 3 2
خروجی نمونه ۱
1
توضیح نمونه اول:
سالارخان به خانوار اول ۱ کیلو نخود و به هر یک از خانوار دوم و سوم ۲ کیلو نخود می‌دهد، در نتیجه تنها یک ناسزا از خانوار دوم نثارش می‌شود.
ورودی نمونه ۲
10 4
4 5 2 3
خروجی نمونه ۲
4
ارسال پاسخ برای این سؤال