Maşınla səyahət - 2
İlk öncə n şəhər var. Siz 1-ci şəhərdən n-ci şəhərə avtomobillə getmək istəyirsiniz. Bunun üçün benzin almaq lazımdır. Məlumdur ki, k-cı şəhərdə bir litr benzinin qiyməti cost[k]-dir. Əvvəlcə yanacaq çəniniz boşdur və siz hər kilometr üçün bir litr benzin sərf edirsiniz. Şəhərlər artan sırayla bir xətt üzərində yerləşir, burada k-cı şəhərin koordinatı x[k]-dir. Həmçinin k-cı şəhərə daxil olmaq üçün toll[k] ödəməlisiniz. Sizin vəzifəniz - mümkün olan ən az xərclə səyahəti həyata keçirməkdir.
Giriş məlumatları
Birinci sətir şəhərlərin sayını n (1 ≤ n ≤ 10^5) ehtiva edir.
İkinci sətir şəhərlərin n koordinatları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ədləri ehtiva edir - benzinin qiymətləri cost[1], ..., cost[n].
Dördüncü sətir n tam ədədləri ehtiva edir - giriş rüsumları toll[1], ..., toll[n].
Məlumdur ki, şəhərlərin koordinatları, benzinin qiymətləri və giriş rüsumları 10^9-u keçməyən qeyri-mənfi tam ədədlərdir.
Çıxış məlumatları
Səyahətin mümkün olan ən az xərclə qiymətini çıxış edin.