غول غارنشین در دهانش $n$ جفت دندان دارد که از $1$ تا $n$ شماره گذاری شده‌اند. طول $i$امین دندان بالای غول $u_{i}$ و طول $i$امین دندان پایین این غول $d_{i}$ است. به دلیل عدم مراقبت، نظم دندان‌های غول غارنشین به شدت به هم ریخته است و دیگر نمی‌تواند به خوبی غذا را بجود. به همین دلیل وی تصمیم گرفته به دندان‌پزشک مراجعه کند. دندان‌پزشک دو نوع کار می‌تواند برای غول غارنشین انجام دهد: افزایش ارتفاع یک دندان به اندازه‌یک واحد که هزینه $A$ دارد و کاهش ارتفاع یک دندان به اندازه‌یک واحد که هزینه $B$ دارد. دندان‌پزشک ارتفاع دندان‌های موردنظر غول را به اندازه موردنیاز غول تغییر می‌دهد.

غول غارنشین که پس انداز زیادی ندارد، می‌خواهد تا حد امکان در هزینه‌ها صرفه‌جویی کند. او می‌داند که اگر حداقل $k$ عدد $1 \le i_{1} < i_{2} < \dots < i_{k} \le n$ وجود داشته باشند به طوری به‌ازای هر $p, q \in {1, \dots, k}$ داشته باشیم $d_{i_{p}}+u_{ i_{p}}=d_{ i_{q}}+u_{ i_{q}}$ در این صورت دندان‌های غول در وضعیت مناسب قرار دارد. غول می‌خواهد با کمترین هزینه دندان هایش را در وضیعت مناسب قرار دهد. اما از آن‌جایی که مغز غول به اندازه هیکلش بزرگ نیست، از شما برای انجام این کار کمک خواسته است.

• در سطر اول ورودی به ترتیب چهار عدد صحیح $n$ ،‌$k$ ، $A$ و $B$ آمده است.
• دو سطر بعدی هر یک شامل $n$ عدد صحیح مثبت هستند که به ترتیب نشان دهنده اندازه دندان‌هایی بالایی و پایینی غول هستند.
• $1 \leq k \leq n \leq 2 \times 10^5$
• $1 \leq A,B \leq 1000$
• تمام اعداد ورودی بین ۰ و $10^6$ هستند
• در حداقل ۲۰ درصد تست ها مقدار $n$ کمتر یا مساوی ۲۰۰۰ است

در یک سطر یک عدد در خروجی چاپ کنید که نشان دهنده کمترین هزینه‌ایست که غول باید هزینه کند تا دندان‌هایش در وضعیت مناسب قرار گیرند. دقت کنید که امکان دارد این عدد از $2^{32}$ بیشتر باشد.

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

در تست اول باید ارتفاع هر سه جفت دندان برابر شود. یکی از بهترین راه‌ها برای این کار افزایش ارتفاع دندان $d_{1}$ به اندازه دو واحد و کاهش ارتفاع دندان $d_{3}$ به اندازه دو است که هزینه مجموع $6$ دارد.