Problem Description

A “match item” is defined as a string of length $L$, where each position is either $\texttt{0}$ or $\texttt{1}$. Now there are $N$ such “match items”. We want to design a “plan”, which is also a string of length $L$, and each position is either $\texttt{0}$ or $\texttt{1}$.

For each “match item”, define its error value as the number of positions where the “plan” differs from the “match item”. For example, if the “match item” is $\texttt{101}$ and the “plan” is $\texttt{000}$, then the first and third positions are different, so the error value of this “plan” for that “match item” is $2$.

We want to find a “plan” that minimizes the sum of error values over these $N$ “match items”. In addition, there are $M$ distinct forbidden “plans”, and the “plan” we find must not be one of the forbidden “plans”.

Input Format

The first line contains three positive integers $N, M, L$.

Then there are $N$ lines, each being a string of length $L$. After that, there are $M$ lines, each being a string of length $L$.

Output Format

Output one integer, the minimum possible sum of error values over the $N$ “match items” achieved by a valid “plan”.

4 1 4
0000
1000
1100
1010
1000

5

2 4 4
0000
0000
0000
1000
0100
0010

2

Hint

It is guaranteed that $1 \le N \le 1000$, $1 \le M \le \min(1000, 2^L - 1)$, $1 \le L \le 1000$.

Translated by ChatGPT 5