cho.sh

Palindrome Matrix

Flip the fewest bits in an even-by-even 0/1 matrix so that at least R rows and at least C columns read as palindromes.

Hard8Bit manipulationBrute forceDynamic programmingNo attempts yetTime limit2sMemory limit512 MB

Problem

You are given a matrix A with N rows and M columns. Both N and M are even, and every element of the matrix is 0 or 1.

Rows are numbered 1 to N from the top, and columns are numbered 1 to M from the left.

A palindrome is a string that reads the same forward and backward. For example, "1001" and "0111001110" are palindromes, while "1101" and "000001" are not.

Each row and each column is read as a string of 0s and 1s, so it is either a palindrome or not. In the matrix below, row 1 is "0000" and column 4 is "0110", and both are palindromes.

0000
0011
0111
1110

You are given the matrix A and two integers R and C. Changing one element means flipping a 0 to a 1, or a 1 to a 0. Write a program that finds the minimum number of elements you have to change so that at least R rows are palindromes and at least C columns are palindromes.

Input

The first line contains N, M, R, and C, separated by spaces. (2≤N,M≤142 \le N, M \le 14, N and M are even, 0≤R≤N0 \le R \le N, 0≤C≤M0 \le C \le M)

Each of the next N lines contains one row of A, starting from row 1. Each line is a string of length M made of 0 and 1.

Output

Print the minimum number of elements you have to change so that at least R rows of A are palindromes and at least C columns are palindromes.