eolymp
bolt
Try our new interface for solving problems
Problems

Мутация

Мутация

Time limit 1 second
Memory limit 256 MiB

Учёные планеты Олимпия проводят эксперимент по генной мутации подопытного примитивного организма в целевой примитивный организм. Геномы организмов могут быть представлены в виде последовательности генов, а кождый ген кодируется цифрой 0 или 1. Эксперимент проводится поэтапно. На каждом этапе в геноме подопытного организма некоторые гены изменяются на противоположные (т.е. 0 на 1 и наоборот). Учёные могут выбирать какие именно гены изменять, но их количество на каждом етапе фиксировано. Это количество обусловлено биологически и задано для каждого этапа мутации отдельно. Геномы подопытного и целевого примитивных организмов состоят из одинакового количество генов. Известно, что геномы состоят из определённого количество повторений одной и той же последоватености генов, называемой базисной.

Напишите программу, которая по заданным геномам подопытного и целевого примитивных организмов, а также по количествам генов, которые изменяются на каждом етапе эксперимента найдёт наименьшее количество этапов мутации генома подопытного организмв в геном целевого организма.

Input data

Первая строка содержит четыре целых числа A, B, N и M (1 A 40000, 1 B 40000, 1 N2×10^9, 1 M 100000). A, B - длины базисных последовательностей генов соответственно подопытного и целевого примитивных организмов. Число N – длина геномов обеих организмов; гарантируется, что число N нацело делится и на A, и на B. Число M - максимальное количество этапов мутации, которое учёные могут провести. Вторая и третья строки содержат базисны последовательности для подопытного и целевого примитивных организмов, состоят только из 0 и 1 и имеют длины A и B соответственно. i-ая с последующих M строк содержит натуральное число, не превышаюее N – количество генов, которые будут изменены на i-м этапе. Гарантируется, что мутацию можна завершить за M, или за меньшее количество этапов.

Output data

Вывести одно целое число - искомое минимальное количество этапов мутации, за которое учёным удастся получить геном целевого организма из генома подопытного.

Examples

Input example #1
2 3 6 4
01
110
1
3
1
2
Output example #1
3
Author Yaroslav Tverdohleb
Source 2010 XXIII All-Ukrainian Informatics Olympiad, Kiev, March 22 - 26, Round 1