102492: [AtCoder]ABC249 C - Just K

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

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

分数:300分

问题描述

给你 $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$ 时,字母 abc 恰好在两个字符串中出现。

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


样例输入 2

2 2
a
b

样例输出 2

0

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


样例输入 3

5 2
abpqxyz
az
pq
bc
cy

样例输出 3

7

加入题单

上一题 下一题 算法标签: