Yağış
Batumi həmişə günəşli olmur: dəniz sahilində yerləşdiyi üçün bəzən şəhərə gözlənilmədən güclü fırtına gələ bilər. Vekua Kubokunun təşkilatçılarından biri olan Rezo, qonaqların şəhərlərarası avtobusla gəlməsini avtovağzalda gözləyirdi. Bu zaman güclü yağış başladı. Çöldə dayanmaq mümkün deyildi, avtovağzalın içində isə təmir işləri aparılırdı. Rezo, avtovağzalın divarında asılmış şəhər avtobuslarının bütün dayanacaqlardakı tam cədvəlinə diqqət yetirdi. O, belə düşündü: əgər bu marşrutun avtobusuna stansiyada minib, bir neçə dayanacaq gedib, sonra düşüb eyni marşrutun əks istiqamətində gedən avtobusuna minib, qonaqların gəlməsinə qədər avtovağzala qayıda bilər. Rezo yağış altında mümkün qədər az vaxt keçirmək istəyir.
Sizin vəzifəniz bu vaxtı hesablamaqdır.
Giriş verilənləri
Giriş faylının ilk sətirində 5 ədəd t_1, t_2, m, n_1, n_2 (0 ≤ t_1 ≤ t_2 ≤ 10^9, 2 ≤ m ≤ 1000, n_1, n_2 ≥ 1, m·(n_1+n_2) ≤ 10^6) verilir. Burada, t_1 - yağışın başlama vaxtı, t_2 - qonaqların avtovağzala gəlmə vaxtı, m - şəhər avtobusunun marşrutundakı dayanacaqların sayı (avtovağzal daxil olmaqla), n_1 və n_2 - avtovağzaldan gedən və avtovağzala gələn şəhər avtobusunun reyslərinin sayı müvafiq olaraq. Marşrutun son nöqtələri avtovağzal və m nömrəli dayanacaqdır, son nöqtədə avtobusda qalmaq olmaz. Sonra m sətirdə hər bir dayanacaq üzrə avtobusların cədvəli verilir, ardıcıl olaraq avtovağzaldan son dayanacağa qədər - n_1+n_2 qeyri-mənfi tam ədədlər, 10^9-u keçməyən. İlk n_1 ədəd avtovağzaldan gedən avtobusların yola düşmə vaxtını göstərir: i-ci ədəd həmin dayanacaqdan i-ci "birbaşa reysin" gəlmə və yola düşmə vaxtını göstərir, növbəti n_2 - avtovağzala gedən avtobusların gəlmə və yola düşmə vaxtını göstərir: (n_1+i)-ci ədəd həmin dayanacaqdan i-ci "geri reysin" yola düşmə vaxtını göstərir. Avtobusun dayanacağa gəlməsi və yola düşməsi eyni vaxt vahidində baş verir, xüsusilə. Rezo yalnız bir avtobusun dayanacağa gəlmə vaxtı digər avtobusun gəlmə vaxtını keçmədikdə avtobusdan avtobusa keçə bilər.
Çıxış verilənləri
Bütün ədəd çıxarın - komandanın gəlməsinə qədər Rezonun məcburən yağış altında keçirəcəyi minimum vaxt.