33266번 - Generate Optimal Key 다국어

문제

A pattern is defined as a binary string of length $L$. Given $n$ patterns, we want to find a key which is also a binary string of length $L$.

For a given pattern and a given key, the error value is defined as the number of positions where the key differs from the pattern. For example, if the pattern is 101, and the key is 000, then the first and third positions are different, so the error value is 2ドル$.

We want to find a key such that the sum of the error values for this key and the given $n$ patterns is minimized. Additionally, there are $m$ distinct forbidden keys, and the key we find cannot be one of the forbidden keys.

입력

The first line of input contains three integers, $n,ドル $m,ドル and $L$ (1ドル \le n \le 1000$; 1ドル \le m \le \min(1000, 2^L - 1)$; 1ドル \le L \le 1000$).

Each of the following $n$ lines represents a pattern and contains a binary string of length $L$.

Each of the following $m$ lines represents a forbidden key and contains a binary string of length $L$. All forbidden keys are distinct.

출력

Output a single integer: the minimum sum of error values for a non-forbidden key and the $n$ given patterns if we select the key optimally.

제한

힌트