کارخانه‌ی پفک‌سازی برای رفاه کارکنانش، هزینه‌‌ی رفت و آمد آن‌ها را تقبل کرده است. کارکنان برای رفت و آمد می‌توانند از تاکسی‌های شخصی و یا اتوبوس‌های مخصوص کارخانه استفاده کنند. کارخانه و خانه‌ی کارمندان همه در یک خیابان بلند قرار دارند و کارخانه در نقطه‌ی صفر خیابان قرار گرفته است. مختصات خانه‌ها می‌تواند منفی باشد. هزینه‌ی استفاده از تاکسی به ازای هر متر برابر ۱ تومان است، در صورتی که استفاده از اتوبوس‌های کارخانه، رایگان هستند. تنها هزینه‌ای که حمل و نقل اتوبوس‌ها بر کارخانه تحمیل می‌کند، نگهداری از ایستگاه‌های اتوبوس است (از هزینه‌ی ساخت ایستگاه صرف نظر می‌شود). هزینه‌ی نگهداری از ایستگاه اتوبوس را $c$ تومان در نظر بگیرید. هم‌چنین می‌دانیم بدون استفاده از تاکسی‌ها و تنها با استفاده از اتوبوس‌ها، می‌توان از هر ایستگاه اتوبوسی به هر ایستگاه دیگری رسید.

حال مسئولین کارخانه قصد دارند تعدادی ایستگاه اتوبوس درست کنند به طوری که هزینه‌ی روزانه‌ای که باید بابت حمل و نقل پرداخت کنند، کمینه شود. فرض می‌شود که تمامی کارکنان توسط ارزان‌ترین مسیر به خانه‌شان می‌روند. بنابراین اگر تعداد ایستگاه‌های ساخته شده را $k$ بگیریم و مجموع مسافتی که کارمندان از تاکسی استفاده خواهند کرد برابر با $t$ باشد (با این فرض که همه‌ی کارمندان در ابتدا در خانه‌ی صفر هستند و کارمند شماره‌ی $i$‌قصد دارد به مختصات $x_i$ برود)، هزینه‌ی کارخانه مساوی $kc+t$ می‌شود.

برنامه‌ای بنویسید که کم‌ترین هزینه برای رفت و ‌آمد کارکنان را محاسبه کند.

در سطر اول ورودی دو عدد طبیعی $n$، تعداد کارکنان و $c$، هزینه‌ی نگهداری از یک ایستگاه اتوبوس آمده است.($1\leq n \leq 10^6$ و $1\leq c \leq 10^9$)

سطر دوم شامل $n$ عدد صحیح $x_1,x_2,…,x_n$ است به طوری که $x_i$ مکان خانه‌ی کارمند $i$- ام را نشان می‌دهد.($-10^9 \leq x_1,x_2,…,x_n\leq 10^9$)

درتنها سطر خروجی هزینه‌ای که کارخانه باید برای رفت و آمد روزانه بپردازد را چاپ کنید.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

در ورودی نمونه‌ی اول، به دلیل هزینه‌ی زیاد ایستگاه اتوبوس، حالت بهینه این است که همه‌ی کارمندان تنها از تاکسی استفاده کنند در این صورت هزینه برابر می‌شود با : $10+20+30+40=100$.

در ورودی نمونه دوم، یکی از حالت‌های بهینه ساخت سه ایستگاه اتوبوس در مکان‌های ۵۰-، ۰ و ۵۰ است، در این صورت کارمندان در مجموع با ۳۶ تومان به مقصدهایشان می‌رسند.

• سوال بعد
• سوال قبل