+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آرایه $a$، شامل اعداد $a_1, a_2, ..., a_n\ $ روی تخته نوشته شده است. در هر گام می‌توانیم یکی از دو عملیات زیر را انجام دهیم. + یک عدد $x$ از روی تخته در نظر بگیریم و **تمام** اعداد $x$ روی تخته را با $\left \lfloor{ \frac {x}{2}}\right \rfloor$ جایگزین کنیم. (یعنی به جای هر $x$ روی تخته، $\left \lfloor{ \frac {x}{2}}\right \rfloor$ قرار می‌دهیم.‌) + یک عدد $x$ از روی تخته در نظر بگیریم و **تمام** اعداد $x$ روی تخته را پاک کنیم. از عملیات نوع دوم **حداکثر $k$ بار** می‌توانیم استفاده کنیم. کم‌ترین تعداد مرحله برای این که در انتها کلا عددی روی تخته باقی نماند، یا تمامی اعداد باقی مانده برابر با $0$ باشد، چه‌قدر است؟ # ورودی ورودی شامل دو خط است که خط اول آن شامل دو عدد $n, k$ است. در خط دوم $n$ عدد $a_1, a_2, .., a_n\ $ می‌آید که اعداد اولیه روی تخته را مشخص می‌کند. $$1 \le n \le 100\ 000$$ $$0 \le k \le 10$$ $$1 \le a_i \le 10^9$$ # خروجی در تنها خط خروجی کمترین مراحل مورد نیاز برای رسیدن به شرایط مطلوب را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 2 1 2 3 4 5 ``` ## خروجی نمونه ۱ ``` 5 ``` یکی از روش‌ها این است که ابتدا اعداد $5$ و $4$ را با عملیات نوع اول به $2$ تبدیل کنیم. سپس عدد $3$ را به $1$ تبدیل کنیم، اعداد روی تخته $<1, 2, 1, 2, 2>$ خواهند بود. در نهایت عدد $1, 2$ را پاک کنیم و دنباله تهی می‌شود. در مجموع $5$ عملیات انجام شده است. ## ورودی نمونه ۲ ``` 4 1 1 1 2 3 ``` ## خروجی نمونه ۲ ``` 3 ``` در یکی از روش‌های بهینه ابتدا عدد $3$ را حذف می‌کنیم،‌ سپس $2$ را با عملیات اول به $1$ تبدیل می‌کنیم و نهایتا همه اعداد $1$ را با عملیات اول به صفر تبدیل می‌کنیم. ## ورودی نمونه ۳ ``` 10 3 10 20 30 40 50 60 70 80 90 100 ``` ## خروجی نمونه ۳ ``` 16 ```

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