- محدودیت زمان: ۴ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
فرزام از بچگی به گل و گیاه علاقه داشت و به همین سبب حالا که بزرگ شده است، در باغچه حیات خود گلدانهای متعدد و زیادی دارد. او سال ها پیش که میخواست گلهای خود را در این گلدانها بکارد، در هر یک از گلدانها مقدار مشخصی خاک ریخت اما اکنون پس از گذشت چند سال، مقدار خاک مورد نیاز این گلها تغییر کرده است.
باتوجه به متفاوت بودن گلهای گلدانهای مختلف، مقدار خاک مورد نیاز آنها هم متفاوت است. برخی از گلها در طی این چند سال نیازشان به خاک افزایش یافتهاند، اما برخی نیز ممکن است نیاز آنها کاهش یافته باشد.
فرض کنید، گلدانها با شمارههای ۱ تا \(N\) که \(1 \leq N \leq 100\) به ترتیب در یک سطر قرار گرفته باشند و مقدار اولیه خاک هر گلدان را به ترتیب \(A_i\) مینامیم. هم چینن مقدار خاک جدید مورد نیاز هر گلدان را به ترتیب \(B_i\) مینامیم. فرض کنید خاک موجود در گلدانها در طی این چند سال تغییری نکرده باشد و همه \(A_i\) و \(B_i\)ها در بازه صفر تا ۱۰ باشند.
میدانیم به هر یک از سه طریق زیر میتوان مقدار خاک یک گلدان را تغییر داد.
-
میتواند ۱ واحد خاک بخرد و آن را در هریک ار گلدانها که بخواهد بریزد. هزینه این عمل به طور ثابت برابر \(X\) است.
-
میتواند ۱ واحد از خاک یک گلدان دلخواه را با هزینه ثابت \(Y\) از گلدان مورد نظر برداشته و دور بریزد.
-
میتواند یک واحد خاک را از گلدان \(i\) به گلدان \(j\) منتقل کند. هزینه این عمل برابر \(Z \times |i-j|\) خواهد بود.
میخواهیم خاک هر گلدان مقدار مورد نیاز جدید شود. حداقل هزینه مورد نیاز برای انجام این کار با توجه به مقادیر ورودی چقدر است؟
ورودی
در خط اول ورودی ۴ عدد \(N, X, Y, Z\) میآیندکه با یک فاصله از هم جدا شدهاند.
\[1 \leq X,Y,Z \leq 1\ 000\]
در خطهای \(2, ..., N+1\) در هر خط دو عدد میآید به طوری که در خط \(i+1\)ام، به ترتیب دو عدد \(A_i\) و \(B_i\) میآیند که با یک فاصله از هم جدا شدهاند.
خروجی
در تنها سطر خروجی حداقل هزینهای که با آن میتوان به حالت مورد نظر رسید را چاپ کنید.
مثال
ورودی نمونه
4 10 200 1
1 4
2 3
3 2
4 0
خروجی نمونه
210