3733. 字母游戏

单点时限: 2.0 sec

内存限制: 256 MB

“由于天气原因,今天航路会一路颠簸,所有机上的服务将会暂停。”

空乘人员没有了服务的工作,在飞行途中就没有固定的工作安排了。

Cuber QQ 为了打发无聊的飞行时间,和空乘玩起了游戏。

不妙的是,空乘似乎要比 Cuber QQ 厉害许多。Cuber QQ 自然是不认为有人比他厉害的,他想打压一下空乘人员。

Cuber QQ 最近正好打算重修《离散数学》,他想出了一个和等价类相关的游戏。

他允许空乘写出任意的 $k$ 个关系,关系是表示两个字母是等价的,例如一个关系可以是字符 a 和字符 b 是等价的。

Cuber QQ 又规定这 $k$ 个等价关系是满足传递关系的,例如一个关系是字符 a 和字符 b 是等价的;另一个关系是字符 a 和字符 c 是等价的,那么可以得到字符 b 和字符 c 也是等价的。

现在 Cuber QQ 会给出 $n$ 个字符串,他定义两个长度字符串 $S_1$ , $S_2$ 是等价的,当且仅当这两个字符串长度相同,而且对于每一位,$S_1$ 的字符和 $S_2$ 的字符都是等价的。

Cuber QQ 现在规定如果两个字符串是等价的,他们就成为一个等价的字符串对。

现在 Cuber QQ 和空乘要分别写出自己的 $k$ 个等价关系,然后通过比较谁给出的关系可以使得等价字符串对的数量更大,谁就是胜利者。

Cuber QQ 想知道,如果合理地写出 $k$ 个等价关系,等价字符串对的数量最大能是多少。

输入格式

第一行三个整数 $n,m,k(2\le n\le 1000,1\le m\le 1000,0\le k\le 1000)$ ,分别表示字符串的数量,每一个字符串的长度和关系的限制数量。

接下来 $n$ 行,每行一个长度为 $m$ 的字符串,字符串仅包含前八个小写字母,即 abcdefgh

输出格式

输出一个整数表示答案。

样例

Input
3 3 1
aaa
aab
bba
Output
3

提示

样例解释:

我们只需给出字母 a 等价于字母 b 这一个等价关系,就可以使得给出的这三个字符串全部等价,所以等价字符串对的数量为 $C_3^2=3$ 。

20 人解决,52 人已尝试。

24 份提交通过,共有 405 份提交。

6.8 EMB 奖励。

创建: 11 月前.

修改: 11 月前.

最后提交: 7 月,1 周前.

来源: N/A

题目标签