Palindrome Matrix

Time limit2sMemory limit512 MB

Summary

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.

Level: Hard8 of 10
Topics: Bit manipulation, Brute force, Dynamic programming
Solved: No attempts yet

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.

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 \le N, M \le 14$ , N and M are even, $0 \le R \le N$ , $0 \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.

Examples4

Example 1
Input
```
4 4 2 2
0000
1000
1100
1110
```
Expected output
```
1
```
Example 2
Input
```
4 4 3 2
0000
1000
1100
1110
```
Expected output
```
3
```
Example 3
Input
```
2 2 1 1
01
10
```
Expected output
```
1
```

Example 4

Input

Expected output