Maşınla səyahət#10776
Verilən şəhər var. Siz -ci şəhərdən -ci şəhərə maşınla getmək istəyirsiniz. Bunun üçün benzin almalısınız. Məlumdur ki, -cı şəhərdə bir litr benzinin qiyməti cost_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, -cı şəhərin koordinatı x_k-dır. Həmçinin -cı şəhərə daxil olmaq üçün toll_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.
Birinci sətir şəhərlərin sayını ehtiva edir n~(1 \le n \le 1000).
İkinci sətir şəhərlərin 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 tam ədəd ehtiva edir — benzinin qiymətləri cost_1, ..., cost_n.
Dördüncü sətir tam ədəd ehtiva edir — giriş rüsumları toll_1, ..., toll_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.
Səyahətin mümkün olan ən aşağı qiymətini çıxarın.
Nümunə 1