{"raw_statement":[{"iden":"background","content":"翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) B 题。"},{"iden":"statement","content":"你与一些好友一起举办了一个舞会！\n\n在这个舞会上，有 $n$ 位男性和 $m$ 位女性，本来舞蹈的形式是一男一女跳的，但是由于男性紧缺，你并不能让所有女性都有一个男性舞伴，于是你发明了一种新的舞蹈形式：一个男性，搭配两个女舞伴。\n\n当然，每个女性在挑选舞伴时，都会对那些男性舞伴做出评价，如果评价是 $1$，说明这位女性愿意和这位男性一起跳舞，只有当两位女性都愿意和那位男性跳舞时，才能成为一对舞伴。\n\n你作为一个组织者，自然要为大家着想，你需要求出能凑出的最多的舞伴对数，**每个舞伴不能重叠**。"},{"iden":"input","content":"第一行一个数 $t (1 \\leq t \\leq 20)$，表示数据组数。\n\n接下来 $t$ 组数据，每组第一行两个整数 $n$ 和 $m$，此处我们保证 $1 \\leq n,m$ 且 $n + m \\leq 150$。\n\n然后一个 $n \\times m$ 的矩阵，$a_{i,j}$ 表示 $j$ 号女士是否愿意和 $i$ 号男士一起跳舞。"},{"iden":"output","content":"对于每组测试数据，输出一行，表示最多能凑出的舞伴对数。"},{"iden":"note","content":"数据保证 $1 \\leq t \\leq 20$，$1 \\leq n, m$ 且 $n + m \\leq 150$。\n\n下图是对样例一和样例二的解释，其中加粗部分表示其中的一种可行方案。\n\n样例一：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/9dfwv4dr.png)\n\n样例二：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/woscpjcn.png)"}],"translated_statement":null,"sample_group":[["2\n2 3\n111\n111\n3 4\n0110\n1100\n0011","1\n2"],["1\n3 6\n001100\n111111\n001100","2"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}