// 状态： f[i][j][k]
//  前 i 位数，花费 k 个， 余数 为 j ， 的方案数
//  第 i 位： 枚举第 i 位调整成多少
//f[i][新的余数][花费]  += f[i - 1][之前的余数][之前的花费]
#include <bits/stdc++.h>
using namespace std;
char s[30];
int m, n;
long long f[30][11][505];

int main() {
	cin >> s + 1 >> m;

	f[0][0][0] = 1;
	n  = strlen(s + 1);
	for (int i = 1; i <= n; i++) {  // 枚举每一位
		for (int j = 0; j < 11; j++) {  // 枚举余数
			for (int k = 0; k <= m; k++) {
				// 枚举 当前位置要变成的值
				for (int t = 0 ; t <= 9; t++) {  // 当前位置 i , 要变成 新的一个数字 t
					f[i][(j * 10 + t) % 11][k + abs(s[i] - '0' - t)] += f[i - 1][j][k];
				}
			}
		}
	}
	long long ans = 0;
	for (int k  = 0 ; k <= m ; k++)
		ans += (m - k) * f[n][0][k];
	cout << ans;
	return 0;
}

// 状态：f[i][j] 前 i个物品，重量是j,最大价值为 f[i][j]
// 转移方程： 每一个物品，选或者不选
//1. 不选：f[i][j] = f[i-1][j]
//2. 选择： f[i][j] = f[i-1][j-w[i]]+v[i]  (j>=w[i])
//  j - w[i] 预留出存放第 i 个物品的空间
//  放 第 i 个物品： j-w[i] + w[i] == j
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int M = 2e4 + 10;
int n, m;
int w[N], v[N];
int f[M];

int main() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];
	// 01 背包，滚动数组
	for (int i = 1; i <= n; i++)
		// 01背包， 遍历容量的时候，倒着遍历
		for (int j = m; j >= w[i]; j--)
			f[j] = max(f[j], f[j - w[i]] + v[i]);
	cout << f[m];
	return 0;
}
//动态规划：
//状态定义
//状态转移：状态转移方程
//初始化：最开始的基准，这个状态是别人推导不出来的，
//遍历顺序：状态转移方程一致的，要推导出新的状态，要用到的状态必须是已知的
//          无后效性，   a -> b , a 要已知的，
//优化
// 迭代， 只跟上一个有关