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