输入描述:

第一行两个整数n，k。
接下来一行长度为n的01串，表示初始串。
接下来2^k行，每行一个字符ci和一个整数wi，ci 表示长度为k的01串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符,wi表示对应的第i种方案对应获得的分数。
1 ≤ n ≤ 300,0 ≤ ci ≤ 1,wi ≥ 1,   k ≤ 8

输出描述:

输出一个整数表示答案

备注:

对于100%的数据，保证：