102492: [AtCoder]ABC249 C - Just K

Problem Statement

You are given $N$ strings $S_1,S_2,\dots,S_N$ consisting of lowercase English alphabets.

Consider choosing some number of strings from $S_1,S_2,\dots,S_N$.

Find the maximum number of distinct alphabets that satisfy the following condition: "the alphabet is contained in exactly $K$ of the chosen strings."

Constraints

• $1 \le N \le 15$
• $1 \le K \le N$
• $N$ and $K$ are integers.
• $S_i$ is a non-empty string consisting of lowercase English alphabets.
• For each integer $i$ such that $1 \le i \le N$, $S_i$ does not contain two or more same alphabets.
• If $i \neq j$, then $S_i \neq S_j$.

Input

Input is given from Standard Input in the following format:

$N$ $K$
$S_1$
$S_2$
$\vdots$
$S_N$

Output

Print the answer.

Sample Input 1

4 2
abi
aef
bc
acg

Sample Output 1

3

When $S_1,S_3$, and $S_4$ are chosen, a,b, and c occur in exactly two of the strings.

There is no way to choose strings so that $4$ or more alphabets occur in exactly $2$ of the strings, so the answer is $3$.

Sample Input 2

2 2
a
b

Sample Output 2

0

You cannot choose the same string more than once.

Sample Input 3

5 2
abpqxyz
az
pq
bc
cy

Sample Output 3

7

问题描述

给你 $N$ 个由小写英文字母组成的字符串 $S_1,S_2,\dots,S_N$。

考虑从 $S_1,S_2,\dots,S_N$ 中选择一些字符串。

找出满足以下条件的最大数量的字母： "该字母恰好在所选字符串中的 $K$ 个中出现。"

约束条件

• $1 \le N \le 15$
• $1 \le K \le N$
• $N$ 和 $K$ 是整数。
• $S_i$ 是一个由小写英文字母组成的非空字符串。
• 对于每个整数 $i$，满足 $1 \le i \le N$，$S_i$ 不包含两个或更多相同的字母。
• 如果 $i \neq j$，那么 $S_i \neq S_j$。

输入

输入将以以下格式从标准输入给出：

$N$ $K$
$S_1$
$S_2$
$\vdots$
$S_N$

输出

打印答案。

样例输入 1

4 2
abi
aef
bc
acg

样例输出 1

3

当选择 $S_1,S_3$ 和 $S_4$ 时，字母 a，b 和 c 恰好在两个字符串中出现。

没有一种方法可以选择字符串，使得恰好在 $2$ 个字符串中出现的字母有 $4$ 个或更多，所以答案是 $3$。

样例输入 2

2 2
a
b

样例输出 2

0

你不能多次选择相同的字符串。

样例输入 3

5 2
abpqxyz
az
pq
bc
cy

样例输出 3

7