- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
کاراکترهای کمکی در روز رسمی اعتراض به نمرات امتحان هندسه‌ی پایان‌ترم، هیئتی برای مذاکره با کاراکتر اصلی ۱ می‌فرستند. خوشبختانه کاراکتر اصلی ۱ اهل معامله است و حاضر است دو نوع معامله با هیئت مذاکره‌کننده انجام دهند:
- نمره‌ی هندسه‌ی $k$ نفر از کاراکترهای کمکی را (به انتخاب هیئت مذاکره‌کننده) از کارنامه‌شان حذف کند و در ازای این‌کار $x \times k$ تومان پول دریافت کند، که $x$ یک عدد طبیعی مشخص و $k$ یک عدد طبیعی دلخواه هستند.
- نمره‌ی هندسه‌ی $k$ نفر از کاراکترهای کمکی را (به انتخاب هیئت مذاکره‌کننده) یک نمره افزایش دهد و در ازای این‌کار $y \times k$ تومان پول دریافت کند، که $y$ یک عدد طبیعی مشخص و $k$ یک عدد طبیعی دلخواه هستند.
توجه کنید هیئت مذاکره‌کننده می‌تواند تنها یک بار از هر نوع معامله استفاده کند.
هدف هیئت مذاکره‌کننده فقط یک چیز است و آن هم این است که لیست نمرات هندسه‌ی کاراکترهای کمکی شرم‌آور نباشد.
لیست نمرات هندسه‌ی کاراکترهای کمکی را شرم‌آور می‌دانیم در صورتی که تهی نباشد (یعنی حداقل نمره‌ی هندسه‌ی یکی از کاراکترهای کمکی در کارنامه‌اش آمده باشد) و ب.م.م (بزرگ‌ترین مقسوم‌علیه مشترک) نمرات ۱ باشد.
در خروجی برنامه‌ی خود چاپ کنید، حداقل میزان پولی که باید کاراکترهای کمکی پرداخت کنند تا لیست نمرات هندسه از شرم‌آوربودن خارج شود، چند تومان است.
ورودی
در خط اول ورودی سه عدد طبیعی $n$، $x$ و $y$ به ترتیب نشان‌دهنده‌ی تعداد نمرات لیست اولیه‌ی نمرات هندسه، ضریب قیمت معامله‌ی اول و ضریب قیمت معامله‌ی دوم داده شده‌اند.
در خط دوم و آخر ورودی، $n$ عدد طبیعی که نشان‌دهنده‌ی لیست اولیه‌ی نمرات هندسه‌ی کاراکترهای کمکی هستند داده شده‌اند. (بیشینه نمره‌ی قابل کسب در امتحان هندسه برای هر نفر $1 \ 000 \ 000 $ است.)
$$1 \leq n \leq 100 \ 000$$ $$1 \leq x,y \leq 1 \ 000\ 000 \ 000$$
خروجی
در تنها خط خروجی کم‌ترین هزینه‌ی ممکن هیئت مذاکره کننده برای رسیدن به هدف را چاپ کنید.
مثال
ورودی نمونه ۱
1 5 1
1
خروجی نمونه ۱
1
ورودی نمونه ۲
1 4 3
8
خروجی نمونه ۲
0
ورودی نمونه ۳
5 7 12
1 2 4 8 16
خروجی نمونه ۳
7
توضیح
در مثال اول ب.م.م (۱) = ۱ در نتیجه یا باید یکی به ۱ اضافه کنیم یا آن را از لیست نمرات حذف کنیم که افزایش نمره در این‌جا ارزان‌تر است.
در مثال دوم لیست اولیه‌ی نمرات هندسه مطلوب است و هیئت‌مذاکره‌کننده بدون پرداخت هزینه‌ای هدف موردنظر را دارد و نیازی به معامله ندارد.
در مثال سوم هرکاری روی هر یک از اعداد لیست نمرات بکنیم ولی روی ۱ تغییری ایجاد نکنیم همچنان ب.م.م اعداد ۱ خواهد بود. پس با افزایش یا حذف روی ۱ در یک معامله می‌توانیم ب.م.م نمرات را به ۲ تغییر بدهیم که در این‌جا حذف ارزان‌تر است از افزایش.
ارسال پاسخ برای این سؤال