Мутация
Учёные планеты Олимпия проводят эксперимент по генной мутации подопытного примитивного организма в целевой примитивный организм. Геномы организмов могут быть представлены в виде последовательности генов, а кождый ген кодируется цифрой 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, или за меньшее количество этапов.
Выходные данные
Вывести одно целое число - искомое минимальное количество этапов мутации, за которое учёным удастся получить геном целевого организма из генома подопытного.