#include<bits/stdc++.h>

using namespace std;

const int N=;

int n,m,tot,ch[N][],fail[N],sz[N],g[N][N],h[N][N];

double w[N],f[N][N];

char T[N],str[N],ans[N];

void insert(int v)

{

    int u=,len=strlen(str+);

    for(int i=;i<=len;++i)

    {

        if(!ch[u][str[i]-''])ch[u][str[i]-'']=++tot;

        u=ch[u][str[i]-''];

    }

    w[u]=log(v),sz[u]+=;

}

void build()

{

    queue<int>q;

    for(int i=;i<;i++)if(ch[][i])q.push(ch[][i]);

    while(!q.empty())

    {

        int u=q.front();q.pop();

        w[u]+=w[fail[u]],sz[u]+=sz[fail[u]];

        for(int i=;i<;i++)

        if(ch[u][i])fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);

        else ch[u][i]=ch[fail[u]][i];

    }

}

void dp(int i,int j,int k)

{

    int c=ch[j][k];

    if(f[i][c]<f[i-][j]+w[c])f[i][c]=f[i-][j]+w[c],g[i][c]=j,h[i][c]=k;

}

bool check(double val)

{

    for(int i=;i<=tot;i++)w[i]-=val*sz[i];

    for(int i=;i<=n;i++)

    for(int j=;j<=tot;j++)

    f[i][j]=-1e300;

    f[][]=;

    for(int i=;i<=n;i++)

    for(int j=;j<=tot;j++)

    if(T[i]=='.')for(int k=;k<;k++)dp(i,j,k);

    else dp(i,j,T[i]-'');

    double ans=-1e300;

    for(int i=;i<=tot;i++)ans=max(ans,f[n][i]);

    for(int i=;i<=tot;i++)w[i]+=val*sz[i];

    return ans>;

}

int main()

{

    scanf("%d%d",&n,&m);

    scanf("%s",T+);

    for(int i=,x;i<=m;i++)scanf("%s%d",str+,&x),insert(x);

    build();

    double l=,r=,mid;

    while(r-l>1e-)

    {

        mid=(l+r)/;

        if(check(mid))l=mid;else r=mid;

    }

    check(l);

    int pos=;

    for(int i=;i<=tot;i++)if(f[n][i]>f[n][pos])pos=i;

    for(int i=n;i;i--)ans[i]=h[i][pos]+,pos=g[i][pos];

    for(int i=;i<=n;i++)putchar(ans[i]);

}