相似替换
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给出 n 种长度为 m 的字符串 s_1,s_2,...\ ,s_n，其中第 i 种字符串 s_i 的出现次数为 c_i。这些字符串仅由 0 和 1 构成。

定义字符串 t 和 p 的相似度为 \sum_{i=1}^{m}(t_i == p_i)\times 2^{m-i}。

你可以执行以下操作任意多次：

\bullet 选择一个字符串 s_i，将 s_i 替换成与 s_i 相似度最高的字符串 s_j \ (j \neq i)。

请求出将所有字符串变成相同字符串的最小操作次数。

输入描述:

第一行包含一个整数 T \ (1 \leq T \leq 65536)，表示测试用例的组数。

每组测试用例的第一行包含两个整数 n,m\ (2\leq n\leq 2^{m} \leq 2^{18})。

每组测试用例的接下来的 n 行，每行包含一个长为 m 字符串 s_i 和一个整数 c_i\ (1\leq c_i \leq 100)，表示有 c_i 个字符串 s_i。保证 n 种字符串各不相同。

对于所有测试用例，保证 n 的总和不超过 2^{18}。

输出描述:

对于每组测试用例，输出一个整数，表示最小操作次数。
示例1

输入

复制 
3
2 2
10 1
01 2
3 3
011 1
101 3
110 2
4 3
100 1
101 2
110 1
111 3

输出

复制 
1
3
5

说明

对于第二组测试用例：110 \rightarrow 101，110 \rightarrow 101，011 \rightarrow 101。
对于第三组测试用例：100 \rightarrow 101，110 \rightarrow 111，101 \rightarrow 111，101 \rightarrow 111，101 \rightarrow 111。