bobo 有一个大小为 $n \times m$ 的二进制矩阵。今天 bobo 打算删除若干行（也可以不删除），以最大化矩阵的“bobo值”（boboness）。

“bobo值”的定义如下：如果第 $i$ 列中 $1$ 的个数为奇数，则将 $a_i \cdot 3^{b_i}$ 加到“bobo值”中，初始值为 $0$。

求“bobo值”的最大值。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \le 200000, 1 \le m \le 70$)。

接下来 $n$ 行，每行包含 $m$ 个整数，表示该矩阵。

最后 $m$ 行，每行包含两个整数 $a_i, b_i$ ($a_i \in \{-1, 1\}, 1 \le b_i \le 35$)。

保证对于所有 $i \neq j$，满足 $a_i \neq a_j$ 或 $b_i \neq b_j$。

输出格式

输出一个整数，表示“bobo值”的最大值。

样例

输入格式 1

2 4
1 1 0 1
0 0 1 0
-1 1
-1 2
1 1
1 2

输出格式 1

3

输入格式 2

1 1
1
-1 1

输出格式 2

0