+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *از آنجایی که هر روز درخواست بچه‌های دوره برای شام طلا بیشتر می‌شد، مجمع شازززیا هر $n$ عضوش را به یک جلسه‌ی سرّی فراخوند تا بتوانند نقشه‌ای بکشند که این داستان را تمام کنند.* هر کدام از شازززیا، نقشه‌ای داشتند و برای اینکه عادلانه تصمیم گیری کنند، در هر جلسه‌ای که بینشان صورت می‌گرفت: - هر کس که می‌خواست نقشه‌اش را ارائه بدهد، $p$ دقیقه زمان نیاز داشت. - برای اینکه رای گیری کنند و بین نقشه‌ها یکی را انتخاب کنند، $v$ دقیقه زمان لازم داشتند. برای مثال اگر در جلسه‌ای $100$ نفر حضور داشته باشند و ارائه نقشه هر کس یک دقیقه طول بکشد $(p = 1)$ و رای گیری هم یک دقیقه طول بکشد $(v = 1)$ جمعاً $100$ دقیقه ارائه نقشه‌ها طول می‌کشد و کلاً $101$ دقیقه که علاوه بر ارائه نقشه‌ها رای گیری هم کنند و یکی را انتخاب کنند. برای تسریع کارشان تصمیم گرفتند که به تعدادی گروه تقسیم شوند و گروه‌ها با هم به طور همزمان کار را پیش ببرند. هر گروه بهترین نقشه را بین اعضای خودش انتخاب می‌کند. بعد نماینده هر گروه نقشه منتخب آن گروه را ارائه می‌دهد و بین نقشه‌های منتخب ارائه شده یکی را انتخاب می‌کنند. برای مثال، اگه $100$ نفر به یک گروه $60$ نفره و یک گروه $40$ نفره تقسیم شوند: - گروه بزرگتر بعد از $61$ دقیقه بهترین نقشه اش را انتخاب می‌کند. - گروه کوچکتر بعد از $41$ دقیقه بهترین نقشه اش را انتخاب می‌کند. - نماینده دو گروه بعد $2$ دقیقه نقشه‌های منتخب گروهشان را ارائه می‌دهند و بعد از $1$ دقیقه رای گیری می‌کنند و بهترین نقشه را انتخاب می‌کنند. کل زمانی که طول کشیده است: $61 + 2 + 1 = 64$ دقیقه. لازم به ذکر است که خود گروه‌ها هم ممکن است به زیر گروه‌هایی تقسیم شوند و بعضی وقت‌ها هم ممکن است تقسیم شدن به بیشتر از دو گروه سودمندتر باشد. بعنوان یک حالت خاص، در یک زیرگروه با فقط یک عضو، تصمیم گیری و انتخاب یک نقشه زمانی نمی‌برد.(چون نیازی نیست نقشه اش را به خودش توضیح بدهد.) همه شازززیا از اولش می‌دانستند که قرار است نقشه آقاتیزی انتخاب شود (نقشه‌ای که در آن قرار است میان دعوای بچه‌ها سر تیم کشی فوتبال، خودش را طرف بچه‌های دوره جا بزند.) ولی آقاتیزی اصرار داشت که برای رعایت عدالت هم که شده، روال انتخاب نقشه به صورت رسمی خودش طی شود. حالا از آنجایی که شازززیا دارند نقشه می‌کشند و وقت کم دارند، از شما خواستند که به صورت خیلی سرّی برنامه‌ای برایشان بنویسید که به ازای ورودی گرفتن $n$ و $p$ و $v$، کمینه زمان که انتخاب بهترین نقشه طول می‌کشد را به آن‌ها بگید. # ورودی به ترتیب $n$ نشان دهنده تعداد افراد، $p$ نشان دهنده زمان مورد نیاز برای ارائه نقشه یک نفر بر حسب دقیقه و در نهایت $v$ نشان دهنده زمان مورد نیاز برای رای گیری بر حسب دقیقه در یک خط ورودی داده می‌شود. $$ 1 \le n \le 10^{15} $$ $$ 1 \le p, v \le 10^9 $$ # خروجی یک عدد خروجی داده شود که برابر کمینه زمان لازم برای انجام مراسم سرّی و انتخاب بهترین نقشه بر حسب دقیقه باشد. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۲۵ | $$ n \le 5\,000 \ \ \ \ \ p,\ v \le 1000 $$ | | ۲ | ۲۰ | $$ n \le 50\,000 \ \ \ \ p,\ v \le 1000 $$ | | ۳ | ۲۵ | $$ p,\ v \le 1000 $$ | | ۴ | ۳۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 9 1 1 ``` ## خروجی نمونه ۱ ``` 8 ``` توضیح نمونه: اعضا می‌توانند به $3$ گروه $3$ نفره تقسیم شوند بعد هر گروه $4$ دقیقه زمان می‌برد و در نهایت نماینده‌های سه گروه هم برای انتخاب نهایی $4$ دقیقه دیگر زمان نیاز دارند. بنابراین پاسخ نمونه برابر $4 + 4 = 8$ است. ## ورودی نمونه ۲ ``` 6 1 2 ``` ## خروجی نمونه ۲ ``` 8 ``` توضیح نمونه: در این نمونه تمام اعضا در یک گروه قرار دارند، $6$ دقیقه زمان ارائه و $2$ دقیقه زمان رای‌گیری لازم است. بنابراین پاسخ نمونه برابر $6 + 2 = 8$ است. ## ورودی نمونه ۳ ``` 6 2 1 ``` ## خروجی نمونه ۳ ``` 12 ``` توضیح نمونه: در این نمونه تمام اعضا به سه گروه دو نفره تقسیم می‌شوند. در هر گروه زمان لازم برای انتخاب بهترین نقشه برابر $5$ است. بعد از این سه نماینده گروه در مدت $7$ دقیقه بهترین نقشه را انتخاب می‌کنند. بنابراین پاسخ این نمونه برابر $5 + 7 = 12$ است.