Задача №111782. Мутация
Учёные планеты Олимпия проводят эксперимент по генной мутации подопытного примитивного организма в целевой примитивный организм. Геномы организмов могут быть представлены в виде последовательности генов, а каждый ген кодируется цифрой 0 или 1. Эксперимент проводится поэтапно. На каждом этапе в геноме подопытного организма некоторые гены изменяются на противоположные (т.е. 0 на 1 и наоборот). Учёные могут выбирать какие именно гены изменять, но их количество на каждом этапе фиксировано. Это количество обусловлено биологически и задано для каждого этапа мутации отдельно. Геномы подопытного и целевого примитивных организмов состоят из одинакового количество генов. Известно, что геномы состоят из определённого количество повторений одной и той же последовательности генов, называемой базисной.
Напишите программу, которая по заданным геномам подопытного и целевого примитивных организмов, а также по количествам генов, которые изменяются на каждом этапе эксперимента найдёт наименьшее количество этапов мутации генома подопытного организмов в геном целевого организма.
Первая строка содержит четыре целых числа \(A\), \(B\), \(N\) и \(M\) (1 ≤ \(A\) ≤ 40000, 1 ≤ \(B\) ≤ 40000, 1 ≤ \(N\) ≤ 2×\(10^9\), 1 ≤ \(M\) ≤ 100000). \(A\), \(B\) - длины базисных последовательностей генов соответственно подопытного и целевого примитивных организмов. Число \(N\) – длина геномов обеих организмов; гарантируется, что число \(N\) нацело делится и на \(A\), и на \(B\). Число \(M\) - максимальное количество этапов мутации, которое учёные могут провести. Вторая и третья строки содержат базисны последовательности для подопытного и целевого примитивных организмов, состоят только из 0 и 1 и имеют длины \(A\) и \(B\) соответственно. \(i\)-ая с последующих \(M\) строк содержит натуральное число, не превышающее \(N\) – количество генов, которые будут изменены на \(i\)-м этапе. Гарантируется, что мутацию можно завершить за \(M\), или за меньшее количество этапов.
Вывести одно целое число - искомое минимальное количество этапов мутации, за которое учёным удастся получить геном целевого организма из генома подопытного.
2 3 6 4 01 110 1 3 1 2
3