Maşınla səyahət

Verilən $n$ şəhər var. Siz $1$-ci şəhərdən $n$-ci şəhərə maşınla getmək istəyirsiniz. Bunun üçün benzin almalısınız. Məlumdur ki, $k$-cı şəhərdə bir litr benzinin qiyməti $cos{t}_k$-dir. Əvvəlcə yanacaq çəniniz boşdur və siz bir kilometrə bir litr benzin sərf edirsiniz. Şəhərlər bir xətt üzərində artan sırayla yerləşir, belə ki, $k$-cı şəhərin koordinatı $x_k$-dır. Həmçinin $k$-cı şəhərə daxil olmaq üçün $tol{l}_k$ ödəmək lazımdır. Sizin vəzifəniz səyahəti mümkün olan ən aşağı qiymətlə başa vurmaqdır.

Giriş verilənləri

Birinci sətir şəhərlərin sayını ehtiva edir $n(1\le n\le 1000)$.

İkinci sətir şəhərlərin $n$ koordinatını ehtiva edir $x_1,...,x_n$. Koordinatlar unikaldır və sıralanmışdır, $x_i<x_{i+1}$ hər bir $i=1,2,...,n-1$ üçün.

Üçüncü sətir $n$ tam ədəd ehtiva edir — benzinin qiymətləri $cos{t}_1,...,cos{t}_n$.

Dördüncü sətir $n$ tam ədəd ehtiva edir — giriş rüsumları $tol{l}_1,...,tol{l}_n$.

Məlumdur ki, şəhərlərin koordinatları, benzinin qiyməti və giriş rüsumları $10^9$-u keçməyən qeyri-mənfi tam ədədlərdir.

Çıxış verilənləri

Səyahətin mümkün olan ən aşağı qiymətini çıxarın.

Nümunələr