وحید می‌خواهد از شهر $a_1$ پس از طی شهرهای $a_2$، $a_3$، …، $a_{n-1}$ (باهمین ترتیب) به شهر $a_n$ برود. در ابتدای سفر یعنی در شهر $a_1$ باک بنزین ماشین او پر است. او مقدار بنزینی که از شهر $a_i$ به $a_{i+1}$ مصرف می‌شود، می‌داند. ضمنا مبلغ هر لیتر بنزین در شهر $a_i$، $c_i$ است. او می‌خواهد با بنزین زدن در بعضی شهرها به مقصد برسد. اما وقتی در یک شهر بیش از نصف باک بنزین ماشین او پر است و می‌تواند به شهر بعدی برسد، دراین شهر بنزین نمی‌زند. ضمنا اگر در یک شهر بنزین بزند، حتما باک بنزین خود را پر می‌کند. او می‌خواهد تصمیم بگیرد در چه شهرهایی باید بنزین بزند تا با حداقل هزینه به مقصد برسد.

الگوریتمی طراحی کنید که با گرفتن ورودی و با استفاده از حافظه‌ی $O(n)$ و در زمان $O(n^2)$ مشکل وحید را حل کند.