====== Gas Stations ====== شما می‌خواهید با استفاده از ماشین خود به یک سفر بروید. مسیری که شما باید طی کنید ‎$l$‎ متر طول دارد. باک ماشین شما حداکثر ‎$k$‎ لیتر بنزین می‌تواند در خود جای دهد و به ازای هر لیتر بنزین ‎$t$‎ متر می‌تواند حرکت کند. در طول راه تعدادی پمپ بنزین وجود دارد که شما می‌توانید از هر کدام از آن‌ها مقداری (نه لزوماً صحیح) بنزین خریداری کنید و در باک خود بریزید. پمپ بنزین ‎$i$‎ام در فاصله ‎$p_i$‎ از شروع حرکت شما قرار دارد و قیمت بنزین آن برابر ‎$c_i$‎ واحد به ازای هر لیتر بنزین است. ‎ باک بنزین شما در ابتدا پر از بنزین است و شما می‌خواهید طوری مسافرت کنید که کم‌ترین هزینه لازم را برای رسیدن به مقصد خود خرج کنید. شما باید برنامه‌ای بنویسید که این کم‌ترین هزینه را به‌دست بیاورد. ===== ورودی ===== * در سطر اول ورودی عدد ‎$1 \leq n \leq 50$‎ نشانگر تعداد پمپ بنزین‌ها آمده است.‎ * در سطر بعدی، اعداد ‎$p_1$‎ تا ‎$p_n$‎ آمده است.‎ * در سطر سوم، اعداد ‎$c_1$‎ تا ‎$c_n$‎ آمده است.‎ * در آخرین سطر، سه عدد ‎$t$‎ و ‎$k$‎ و $l$‎ آمده است.‎ * تمامی اعداد ورودی بین ‎$1$‎ و ‎$20000$‎ اند و ورودی طوری است که شما می‌توانید سفر خود را به پایان برسانید. ===== خروجی ===== در تنها سطر خروجی پاسخ سوال را با دقت ‎1‎ رقم اعشار چاپ نمایید. ===== محدودیت‌ها ===== * محدودیت زمان: ۲ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |2‎ \\ 100 100‎ \\ 1000 1500‎ \\ ‎20 10 300 | 5000.0‎ | |3‎ \\ 300 450 525‎ \\ 1659 1529 1439‎ \\ 20 20 600 | 15277.5 | |3‎ \\ ‎300 450 525‎ \\ 1659 1529 1439‎ \\ ‎20 20 600 | 15277.5‎ | |3‎ \\ 300 450 525‎ \\ 1659 1439 1529‎ \\ ‎20 20 600 | 14940.0 | |4‎ \\ 300 125 450 525‎ \\ 1659 1729 1439 1529‎ \\ 20 20 600‎ | 14940.0 | * [[سوال ۲۸|سوال بعد]] * [[سوال ۲۶|سوال قبل]]