102492: [AtCoder]ABC249 C - Just K
Description
Score : $300$ points
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
Input
题意翻译
给定 $ n $ 个字符串，要求在其中选择任意个。定义字符集为在选择的这些字符串中所有出现次数恰好为 $ k $ 的字母的集合，求最大化的字符集大小。保证字符串中仅有英文小写字母。Output
问题描述
给你 $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