Great! Your new software is almost finished! The only thing left to do is archiving all your $n$ resource files into a big one.
Wait a minute… you realized that it isn’t as easy as you thought. Think about the virus killers. They’ll find your software suspicious, if your software contains one of the $m$ predefined virus codes. You absolutely don’t want this to happen.
Technically, resource files and virus codes are merely
01 strings. You’ve already convinced yourself that none of the resource strings contain a virus code, but if you make the archive arbitrarily, virus codes can still be found somewhere.
Here comes your task (formally): design a
01 string that contains all your resources (their occurrences can overlap), but none of the virus codes. To make your software smaller in size, the string should be as short as possible.
There will be at most $10$ test cases, each begins with two integers in a single line: $n$ and $m$ $(2 ≤ n ≤ 10, 1 ≤ m ≤ 1000)$. The next $n$ lines contain the resources, one in each line. The next $m$ lines contain the virus codes, one in each line. The resources and virus codes are all non-empty
01 strings without spaces inside. Each resource is at most $1000$ characters long. The total length of all virus codes is at most $50000$. The input ends with $n = m = 0$.
For each test case, print the length of shortest string.
- 转移方程就很简单了 $dp[i | val[k]][k] = min(dp[i | val[k])][k], dp[i][j] + dis[j][k])$