Pattengale 教授遇到了一个大问题——他的机器人接收到了错误的数字信号，导致它开始不可预测地乱动！他的电路学生们（“快乐猫”们）得出结论：主板上的导线靠得太近了。当电流通过一根导线时，它会产生磁场，从而在附近的其他导线中感应出电流，导致错误信号。

工程家族发现，原主板有 $N$ 个排成一排的插槽，每个插槽中恰好安装了一根导线。每根导线都有一个范围 $r_i$，覆盖该导线左侧和右侧各 $r_i$ 个插槽；在此范围内的其他导线可能会受到其磁场的影响。每根导线中还传输着一种信号类型 $s_i$。

导线中传输着 $M$ 种不同类型的信号。某些类型的信号会影响其他类型的信号。对于两种不同的类型 $a$ 和 $b$，如果类型 $b$ 的信号会影响类型 $a$ 的信号，那么传输类型 $a$ 信号的导线就不能处于任何传输类型 $b$ 信号的导线的范围内，否则就会产生干扰。如果类型 $b$ 不影响类型 $a$ 的信号，则允许传输类型 $a$ 信号的导线处于传输类型 $b$ 信号的导线的范围内。只有当类型 $b$ 的信号影响类型 $a$ 的信号，且传输类型 $a$ 信号的导线处于传输类型 $b$ 信号的导线的范围内时，才会发生干扰。

类型 $a$ 的信号可能会影响类型 $b$ 的信号，但类型 $b$ 的信号不一定会影响类型 $a$ 的信号。类型 $a$ 的信号也可能会影响其他类型 $a$ 的导线。

工程家族想要为这些导线制作一块新的主板。新主板也将由单排插槽组成。所有 $N$ 根导线在新主板中必须按照与旧主板中相同的从左到右的顺序安装。每个插槽中最多只能安装一根导线。有些插槽可以留空。新主板中必须不能有任何干扰。

给定 $N$ 根导线的原始布局，计算新主板中在不产生干扰的情况下所需的最少插槽数量。

输入格式

输入的第一行包含两个正整数 $N$ 和 $M$（$1 \le M \le N \le 200$）。

接下来的 $N$ 行，每行包含一对整数 $r_i$ 和 $s_i$（$1 \le r_i \le 10^9$，$1 \le s_i \le M$），表示第 $i$ 根导线的范围和信号类型。导线按其在旧主板中从左到右的安装顺序给出。

接下来的 $M$ 行，每行包含一个长度为 $M$ 的二进制字符串。第 $i$ 行描述了哪些信号会影响类型 $i$ 的信号。如果第 $j$ 个字符是 1，则类型 $j$ 的信号不会影响类型 $i$ 的信号。否则（即为 0），类型 $j$ 的信号会影响类型 $i$ 的信号。

输出格式

输出一个整数：新主板为避免干扰所需的最少插槽数量。

样例

输入样例 1

3 3
6 1
3 2
4 3
010
101
100

输出样例 1

6

输入样例 2

3 3
6 1
3 2
4 3
010
100
100

输出样例 2

7

输入样例 3

4 2
4 2
2 1
1 1
4 2
11
10

输出样例 3

6