# Codeforces868c qualification rounds

Posted by yjjr's blog on February 6, 2018

Snark and Philip are preparing theproblemset for the upcoming pre-qualification round for semi-quarter-finals.They have a bank ofn problems, and they want to select any non-emptysubset of it as a problemset.

kexperienced teams are participating in the contest. Some of these teams alreadyknow some of the problems. To make the contest interesting for them, each ofthe teams should know at most half of the selected problems.

Determine if Snark and Philip can make aninteresting problemset!

Input

The first line contains two integersn,k (1 ≤ n ≤ 105, 1 ≤ k ≤ 4) — the number of problems and the number of experiencedteams.

Each of the next n lines contains kintegers, each equal to 0 or 1. The j-th number in thei-th lineis 1 if j-th team knows i-th problem and 0 otherwise.

Output

Print "YES" (quotes for clarity),if it is possible to make an interesting problemset, and "NO"otherwise.

You can print each character either upper-or lowercase ("YeS" and "yes" are valid when the answer is"YES").

Examples

Input

5 3
1 0 1
1 1 0
1 0 0
1 0 0
1 0 0

Output

NO

Input

3 2
1 0
1 1
0 1

Output

YES

Note

In the first example you can't make anyinteresting problemset, because the first team knows all problems.

In the second example you can choose thefirst and the third problems.

Step1首先当然想到的是贪心辣，显而易见，如果这个矩阵中存在一个肯定的答案，那么这个答案肯定可以为2行（如果全都是0的话也可以是一行）

Step2 既然贪心不行，那就双重循环加判断来做呗，TLE on test 54……

Step3 前几天洪老师才讲的位运算唉，这题那么多0和1好像和位运算有些关系（这场CF洪老师也参加了，太劲辣%%%）

Code（正解）

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
int n,k,t,cnt[106],x;
int main()
{
cin>>n>>k;
rep(i,1,n){
t=0;
rep(j,1,k){
scanf("%d",&x);
t=t*2+x;
}
cnt[t]++;
}
rep(i,0,(1<<k))
rep(j,0,(1<<k))
if(cnt[i]&&cnt[j]&&((i&j)==0)){cout<<"YES\n";return 0;}
cout<<"NO\n";
return 0;
}

code（模拟）
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const int maxn=100005;

struct node{int a,b,c,d,sum;}a[maxn];
int n,k,s[5];

inline int cmp(node x,node y){return x.sum<y.sum;}
inline bool check(int x,int y){
if((a[y].a+a[x].a<=1)&&(a[y].b+a[x].b<=1)&&(a[y].c+a[x].c<=1)&&(a[y].d+a[x].d<=1))return true;
else return false;
}

int main()
{
scanf("%d%d",&n,&k);
rep(i,1,n){
if(k==1)scanf("%d",&a[i].a),a[i].sum=a[i].a,s[1]+=a[i].a;
if(k==2)scanf("%d%d",&a[i].a,&a[i].b),a[i].sum=a[i].a+a[i].b,s[1]+=a[i].a,s[2]+=a[i].b;
if(k==3)scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c),a[i].sum=a[i].a+a[i].b+a[i].c,s[1]+=a[i].a,s[2]+=a[i].b,s[3]+=a[i].c;
if(k==4)scanf("%d%d%d%d",&a[i].a,&a[i].b,&a[i].c,&a[i].d),a[i].sum=a[i].a+a[i].b+a[i].c+a[i].d,s[1]+=a[i].a,s[2]+=a[i].b,s[3]+=a[i].c,s[4]+=a[i].d;
}
if(s[1]==n||s[2]==n||s[3]==n||s[4]==n){cout<<"NO\n";return 0;}
sort(a+1,a+1+n,cmp);
int temp=a[1].sum,j=1;
while(a[j].sum==temp){
rep(i,1,n)
if(check(i,j)){cout<<"YES\n";return 0;}
j++;
}
cout<<"NO\n";
return 0;
}