#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=15;
char str[N][M];
int f[N][N];
int editor(char a[],char b[]){
    int la=strlen(a+1),lb=strlen(b+1);
    for(int i=0;i<=lb;i++)f[0][i]=i;
    for(int i=0;i<=la;i++)f[i][0]=i;
    for(int i=1;i<=la;i++){
        for(int j=1;j<=lb;j++){
            f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
            if(a[i]==b[j])f[i][j]=min(f[i][j],f[i-1][j-1]);
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    }
    return f[la][lb];
}


int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%s",str[i]+1);
    while(m--){
        char ss[15];
        int limit;
        int res=0;
        scanf("%s%d",ss+1,&limit);
        for(int i=1;i<=n;i++){
            if(editor(str[i],ss)<=limit)res++;
        }
        printf("%d\n",res);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
char a[N],b[N];
int f[N][N];
int main(){
    cin>>n>>a+1;
    cin>>m>>b+1;
    for(int i=0;i<=m;i++)f[0][i]=i;
    for(int i=0;i<=n;i++)f[i][0]=i;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
            if(a[i]==b[j])f[i][j]=min(f[i][j],f[i-1][j-1]);
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout<<f[n][m];
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=310,INF=0x3f3f3f3f;
int n;
int s[N];
int f[N][N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]+=s[i-1];
    }//前缀和 
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            f[i][j]=INF;
            for(int k=i;k<j;k++){
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
                //表示把i到j合并的最小代价是多少 
            } 
        }
    }
    cout<<f[1][n]; 
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int dp[N][N];
char a[N],b[N];
int  main(){
    int n,m;
    cin>>n>>m;
    cin>>a+1>>b+1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(a[i]==b[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
        }
    }
    cout<<dp[n][m];
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
int a[N];
int q[N];
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    int len=0;
    q[0]=-2e9;
    for(int i=0;i<n;i++){
        int l=0,r=len;
        while(l<=r){
            int mid=l+r>>1;
            if(q[mid]<a[i])l=mid+1;//找到比a[i]小的最大的数放入队列 
            else r=mid-1;
        }
        len=max(len,r+1);
        q[r+1]=a[i];//更新队列 
    }
    cout<<len;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n;
int dp[N],a[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=1;j<=i;j++){
            if(a[i]>a[j]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)res=max(res,dp[i]);
    cout<<res;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int dp[505][505];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>dp[i][j];
        }
    }
    for(int i=n;i>0;i--){
        for(int j=1;j<=i;j++){
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+dp[i][j];
        }
    }
    cout<<dp[1][1];
    return 0;
}