Mutasiya
Olimpiya planetasının alimləri, təcrübəvi primitiv orqanizmin gen mutasiyası ilə hədəf primitiv orqanizmə çevrilməsi üzərində bir eksperiment aparırlar. Orqanizmlərin genomları genlərin ardıcıllığı şəklində təqdim edilir və hər bir gen 0 və ya 1 rəqəmi ilə kodlanır. Eksperiment mərhələli şəkildə aparılır. Hər mərhələdə təcrübəvi orqanizmin genomunda bəzi genlər əksinə dəyişdirilir (yəni, 0 1-ə və əksinə). Alimlər hansı genləri dəyişdirəcəklərini seçə bilərlər, lakin hər mərhələdə dəyişdiriləcək genlərin sayı sabitdir. Bu miqdar bioloji olaraq müəyyən edilir və hər bir mutasiya mərhələsi üçün ayrıca verilir. Təcrübəvi və hədəf primitiv orqanizmlərin genomları eyni sayda gendən ibarətdir. Məlumdur ki, genomlar eyni gen ardıcıllığının müəyyən sayda təkrarlarından ibarətdir ki, bu da əsas ardıcıllıq adlanır.
Təcrübəvi və hədəf primitiv orqanizmlərin verilmiş genomları və eksperimentin hər mərhələsində dəyişdiriləcək genlərin sayına əsasən, təcrübəvi orqanizmin genomunu hədəf orqanizmin genomuna çevirmək üçün lazım olan ən az mutasiya mərhələlərinin sayını tapacaq bir proqram yazın.
Giriş verilənləri
Birinci sətir dörd tam ədəd A, B, N və M (1 ≤ A ≤ 40000, 1 ≤ B ≤ 40000, 1 ≤ N ≤ 2×10^9, 1 ≤ M ≤ 100000) ehtiva edir. A, B - müvafiq olaraq təcrübəvi və hədəf primitiv orqanizmlərin əsas gen ardıcıllıqlarının uzunluqlarıdır. N - hər iki orqanizmin genomlarının uzunluğudur; N ədədinin A və B ədədinə tam bölündüyü təmin edilir. M - alimlərin həyata keçirə biləcəyi maksimum mutasiya mərhələlərinin sayıdır. İkinci və üçüncü sətirlər müvafiq olaraq təcrübəvi və hədəf primitiv orqanizmlərin əsas ardıcıllıqlarını ehtiva edir, yalnız 0 və 1 rəqəmlərindən ibarətdir və uzunluqları müvafiq olaraq A və B-dir. Növbəti M sətirin i-ci sətiri N-dən çox olmayan təbii ədəd ehtiva edir - i-ci mərhələdə dəyişdiriləcək genlərin sayı. Mutasiyanın M və ya daha az mərhələdə tamamlanacağı təmin edilir.
Çıxış verilənləri
Bir tam ədəd çıxarın - alimlərin təcrübəvi orqanizmin genomundan hədəf orqanizmin genomunu əldə etməsi üçün lazım olan minimum mutasiya mərhələlərinin sayı.