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‎ رقم اعشار چاپ نمایید.

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

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