← 返回题目列表

Codeforces · 467/B

B. 费多和新游戏

中文机器翻译题面 查看原题

在你帮助乔治和亚历克斯搬进宿舍后,他们去帮助他们的朋友费多尔玩一个新的电脑游戏《士兵召唤3》。

游戏共有(m+1)名玩家和n种士兵。 《Call of Soldiers 3》玩家的编号从 1 到 (m + 1)。士兵的类型从0到n-1编号。每个玩家都有一支军队。第 i 个玩家的军队可以用非负整数 xi 来描述。考虑 xi 的二进制表示:如果数字 xi 的第 j 位等于 1,则第 i 个玩家的军队拥有第 j 种类型的士兵。

Fedor 是游戏中的第 (m + 1) 位玩家。他假设,如果两个玩家的军队最多有 k 种类型的士兵不同(换句话说,相应数字的二进制表示最多有 k 位不同),那么两个玩家就可以成为朋友。帮助费多并计算有多少玩家可以成为他的朋友。

输入

第一行包含三个整数 n、m、k (1 ≤ k ≤ n ≤ 20;1 ≤ m ≤ 1000)。

接下来的 (m + 1) 行的第 i 行包含一个整数 xi (1 ≤ xi ≤ 2n - 1),它描述了第 i 个玩家的军队。我们提醒您,Fedor 是第 (m + 1) 位玩家。

输出

打印一个整数——Fedor 潜在朋友的数量。

示例

输入 #1

7 3 1
8
5
111
17

输出 #1

0

输入 #2

3 3 3
1
2
3
4

输出 #2

3