AT_abc249_c [ABC249C] Just K

题目描述

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

你可以从 $S_1, S_2, \dots, S_N$ 中任选若干个字符串。

在你选择的字符串中，求“恰好出现在 $K$ 个字符串中的小写英文字母”的种类数的最大可能值。

输入格式

输入以以下格式从标准输入读入。

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4 2
abi
aef
bc
acg

输出 #1

3

输入输出样例 #2

输入 #2

2 2
a
b

输出 #2

0

输入输出样例 #3

输入 #3

5 2
abpqxyz
az
pq
bc
cy

输出 #3

7

说明/提示

限制条件

• $1 \leq N \leq 15$
• $1 \leq K \leq N$
• $N, K$ 均为整数
• $S_i$ 是仅由小写英文字母组成的非空字符串。
• 对于所有满足 $1 \leq i \leq N$ 的整数 $i$，$S_i$ 中同一个字母不会出现两次或以上。
• 若 $i \neq j$，则 $S_i \neq S_j$。

样例解释 1

如果选择 $S_1, S_3, S_4$，那么字母 a、b、c 恰好出现在 $2$ 个字符串中。不存在一种选择方式能让有 $4$ 个或更多的字母恰好出现在 $2$ 个字符串中，因此答案为 $3$。

样例解释 2

同一个字符串不能被选择多次。

由 ChatGPT 4.1 翻译