貌似被卡精度了，但是我调不过去。

此外问一下为啥我把初始编号改成 1 会有点小问题。中间 check 有部分直接把题解粘上去了还是有问题。

#include <iostream>
#include <cassert>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <random>
#include <chrono>
#include <ctime>
#include <map>
#include <set>
using namespace std;
// #define int long long
#define pii pair<int, int>
#define eb emplace_back
#define F first
#define S second
#define test(x) cout << "Test: " << (x) << '\n'
#define lowbit(x) (x & -x)
#define debug puts("qwq")
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define close fclose(stdin);fclose(stdout);
namespace FastIO {
	template <typename T = int>
	inline T read() {
		T s = 0, w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		return s * w;
	}
	template <typename T>
	inline void read(T &s) {
		s = 0;
		int w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		s = s * w;
	}
	template <typename T, typename... Arp> inline void read(T &x, Arp &...arp) {
		read(x), read(arp...);
	}
	template <typename T>
	inline void write(T x, char ch = '\n') {
		if (x < 0) x = -x, putchar('-');
		static char stk[25];
		int top = 0;
		do {
			stk[top++] = x % 10 + '0', x /= 10;
		} while (x);
		while (top) putchar(stk[--top]);
		putchar(ch);
		return;
	}
	template <typename T>
	inline void smax(T &x, T y) {
		if (x < y) x = y;
	}
	template <typename T>
	inline void smin(T &x, T y) {
		if (x > y) x = y;
	}
	void quit() {
		exit(0);
	}
} using namespace FastIO;
const int N = 1555;
const double inf = 1e18, eps = 1e-10;
char s[N], c[N], ans[N];
int n, m, g[N][N][2];
double f[N][N];
struct ACAuto {
	int t[N][10], sum[N], cnt=0, Q[N], fail[N];
	double val[N];
	void insert(char *s, double v) {
		int u=0;
		for (int i=1;s[i];++i) {
			if (!t[u][s[i]-'0']) t[u][s[i]-'0']=++cnt;
			u=t[u][s[i]-'0'];
		} val[u]+=v; sum[u]++; 
	}
	void build() {
		int H=1,T=0;
		for (int i=0;i<=9;++i) if (t[0][i]) {
			fail[Q[++T]=t[0][i]]=0;
		}
		while (H<=T) {
			int u=Q[H++]; sum[u]+=sum[fail[u]]; val[u]+=val[fail[u]];
			for (int i=0;i<=9;++i) if (t[u][i]) {
				fail[t[u][i]]=t[fail[u]][i]; Q[++T]=t[u][i];
			} else t[u][i]=t[fail[u]][i];
		}
	}
} AC;
int check(double x) {
for(int i = 0;i <= AC.cnt;i++) AC.val[i] -= AC.sum[i] * x;
		for(int i = 0;i <= n;i++) for(int j = 0;j <= AC.cnt;j++) f[i][j] = -1e100;
		f[0][0] = 0;
	for(int i = 0;i < n;i++) for(int j = 0;j <= AC.cnt;j++) if(f[i][j] > -1e99)
				for(int k = 0;k < 10;k++) if(c[i+1] == '.' || c[i+1] == k + '0')
				{
					int c = AC.t[j][k];
					if(f[i + 1][c] < f[i][j] + AC.val[c])
					{
						f[i + 1][c] = f[i][j] + AC.val[c];
						g[i + 1][c][0] = j,g[i + 1][c][1] = k;
					}
				}
	for (int i=0;i<=AC.cnt;++i) AC.val[i]+=x*AC.sum[i];
	int pos=0;
	for (int i=0;i<=AC.cnt;++i) if (f[n][i]>f[n][pos]) pos=i;
	for (int i=n,now=pos;i;--i) {
		ans[i]=g[i][now][1]+'0'; now=g[i][now][0];
	}
	return f[n][pos];
}
signed main() {
	read(n, m); scanf("%s",c+1);
	for (int i=1;i<=m;++i) {
		scanf("%s",s+1);
		AC.insert(s,log2(read()));
	} AC.build();
	double L=0,R=log2(inf+19),p;
	while (R-L>eps) {
		double mid=(L+R)/2;
		if (check(mid)>0) L=p=mid;
		else R=mid;
	} check(p);
	printf("%s",ans+1);
	return 0;
}