该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

下发文件

题目描述

给定 $m$ 个 $n$ 位二进制数字 $a_1\cdots a_m$，以及 $m$ 个非负权值 $b_1\cdots b_m$。

另外还有一个 $n$ 位二进制数字 $E$。

请你选出一个子集 $S\subseteq\{1,2,……m\}$，使得

• $\bigoplus\limits_{x\in S}a_x=E$

且 $\sum\limits_{x\in S}b_x$ 尽可能的小。

特别的，我们保证有如下的特殊性质：存在 $1\sim m$ 的排列 $p$，使得 $\forall i=1,2,……m$，至少存在一个二进制位 $k$，使得 $a_{p_i}$ 在第 $k$ 位上是 $1$，且在 $a_{p_1},a_{p_2}……a_{p_{i-1}}$ 中最多有一个数在 $k$ 这一位上是 $1$。

输入格式

第一行两个整数 $n,m$。

第二行一个长度为 $n$ 的 $01$ 字符串描述二进制下的 $E$。

接下来 $m$ 行，每行先输入一个整数 $b_i$，再输入一个长度为 $n$ 的 $01$ 字符串表示二进制下的 $a_i$。

输出格式

一行，一个非负整数代表最小的 $b_x$ 之和，如果不存在满足要求的方案，输出 $-1$。

样例输入

5 8
01110
5 00100
2 01000
8 00001
9 10110
5 00001
4 01111
7 11101
3 01000

样例输出

9

数据规模

• 对于 $20\%$ 的数据，$m\leq 20$。
• 对于 $40\%$ 的数据，$m\leq 40$。
• 对于另外 $20\%$ 的数据，$b_i=1$。
• 对于 $100\%$ 的数据，$n,m\leq 60,1\leq b_i\leq 10^5$。