ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5454: Safe

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：0 通过：0
提交提交记录统计Web Board

题目描述

D. Safe
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Vasya tries to break in a safe. He knows that a code consists of n numbers, and every number is a 0 or a 1. Vasya has made m attempts to enter the code. After each attempt the system told him in how many position stand the right numbers. It is not said in which positions the wrong numbers stand. Vasya has been so unlucky that he hasn’t entered the code where would be more than 5 correct numbers. Now Vasya is completely bewildered: he thinks there’s a mistake in the system and it is self-contradictory. Help Vasya − calculate how many possible code variants are left that do not contradict the previous system responses.
Input
The first input line contains two integers n and m (6≤n≤35,1≤m≤10) which represent the number of numbers in the code and the number of attempts made by Vasya. Then follow m lines, each containing space-separated si and ci which correspondingly indicate Vasya’s attempt (a line containing n numbers which are 0 or 1) and the system’s response (an integer from 0 to 5 inclusively).
Output
Print the single number which indicates how many possible code variants that do not contradict the m system responses are left.
Examples
Input 
6 2
000000 2
010100 4
Output 
6
Input 
6 3
000000 2
010100 4
111100 0
Output 
0
Input 
6 3
000000 2
010100 4
111100 2
Output 
1

输入样例 复制

输出样例 复制

分类标签