Nomyelin buzlu yolları
Sizcə, sürmək asandır? Yollar buzla örtüləndə bu heç də belə deyil.
Nomel şəhərində dəqiq olaraq n + 1 küçə (yollar qərbdən şərqə doğru uzanır) və m + 1 prospekt (yollar şimaldan cənuba doğru uzanır) mövcuddur. Hər bir küçə hər bir prospektlə kəsişir, beləliklə hər bir küçə m bloklara, hər bir prospekt isə n bloklara bölünür.
İndi qışdır və şəhərdəki hər bir yol qalın buz təbəqəsi ilə örtülüb. Buz üzərində sürmək kifayət qədər çətin olduğundan, hər bir yolda bir blokun keçid vaxtı müəyyən edilib. Bu dəyər bir yolun bütün blokları üçün sabitdir.
Təbii ki, yalnız yollarda hərəkət edə bilərsiniz. Sizin vəzifəniz şəhərin şimal-qərb kəsişməsindən cənub-şərq kəsişməsinə ən qısa zamanda çatmaq üçün ən az vaxt tələb edən yolu tapmaqdır. Bu yol həmçinin ən qısa olmalıdır, yəni dəqiq olaraq n + m bloklardan keçməlidir.
Giriş verilənləri
Birinci sətir iki tam ədəd n və m (1 ≤ n, m ≤ 500 000) ehtiva edir. İkinci sətirdə şimaldan cənuba doğru Nomelin küçələrində hərəkət vaxtını göstərən n + 1 təbii ədəd var. Üçüncü sətir qərbdən şərqə doğru Nomelin prospektlərində hərəkət vaxtını göstərən m + 1 təbii ədəd ehtiva edir. Bu ədədlərin heç birinin 10^9 -dan böyük olmadığı təmin edilir.
Çıxış verilənləri
Bir ədəd çıxarın - keçidin mümkün olan ən az vaxtı.