eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Руді пси

Руді пси

\textit{-- Хто йде? -- запитав Фао (у джунглях завжди задають це питання після того, як пролунав фіал). -- Доли, доли, деканські доли! Руді собаки-вбивці! Вони йдуть з півдня, кажучи, що у Декані немає дичини}. Перед походом у сіонійську долину зграя голодних рудих собак вишукувалась у прямокутний бойовий порядок у вигляді прямокутника \textit{\textbf{NxM}} псів. Диким лаєм і жахливим воєм вітали вони свого вожака. Проте вожака така какофонія не вразила, у нього свої погляди на те, як його повинні вітати. Користуючись своєю владою, він може скільки загодно разів віддати команду, щоб у якому-небудь підпрямокутнику бойового порядку розміром \textit{\textbf{KxL}} (довжина сторони по вертикалі рівна \textbf{K}, а по горизонталі \textbf{L}) псів заставити тих хто вив -- лаяти, а тих кто лаяв -- вити. Цікаво, чи зможе він добитись від своєї зграї мелодійного привітання? \InputFile У першому рядку вхідного файлу записано числа \textbf{N, M, K, L (1 ≤ N, M, K, L ≤ 100, K ≤ N, L ≤ M)}. Далі у наступних \textbf{N} рядках записано по \textbf{M} чисел, \textbf{1} -- означає, що собака лає, \textbf{0} -- що собака виє. Ці \textbf{N} рядків задають початкову какофонію. У наступних \textbf{N} рядках у аналогічному форматі записане потрібне мелодійне привітання. \OutputFile У вихідний файл потрібно вивести найменше число команд, які повинен віддати вожак для отримання мелодійного, на його погляд, звучання привітання , або \textbf{-1}, якщо такого набору команд не існує.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
3 3 1 1
0 0 0
1 0 1
0 0 0
0 0 0
0 1 0
0 0 0
Вихідні дані #1
3
Джерело 2010 VII Открытый Чемпионат Харькова, I дивизион, 28 ноября, Задача H