{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eBerSoft是Berland最大的IT公司,Monocarp是其安全部门的负责人。这一次,他面临着有史以来最困难的任务。\u003c/p\u003e\u003cp\u003e基本上,BerSoft有$$$n$$$名开发人员,编号从$$$1$$$到$$$n$$$。内部网络上共享了$$$m$$$份文档,编号从$$$1$$$到$$$m$$$。有一张访问需求表$$$a$$$,其中$$$a_{i,j}$$$(第$$$j$$$行的第$$$i$$$个元素)是$$$1$$$,表示第$$$i$$$个开发人员应该访问第$$$j$$$个文档;是$$$0$$$,表示他们不应该访问它。\u003c/p\u003e\u003cp\u003e为了限制访问,Monocarp将执行以下操作:\u003c/p\u003e\u003cul\u003e\u003cli\u003e选择访问组的数量$$$k \\ge 1$$$;\u003c/li\u003e\u003cli\u003e为每个文档分配一个访问组(一个从$$$1$$$到$$$k$$$的整数)和所需的访问级别(一个从$$$1$$$到$$$10^9$$$的整数);\u003c/li\u003e\u003cli\u003e为每个开发人员分配$$$k$$$个整数值(从$$$1$$$到$$$10^9$$$)—他们对每个访问组的访问级别。\u003c/li\u003e\u003c/ul\u003e\u003cp\u003e如果开发人员的访问级别大于或等于文档的所需访问级别,那么开发人员$$$i$$$就可以访问文档$$$j$$$。\u003c/p\u003e\u003cp\u003eMonocarp可以选择的最小访问组数量是多少,以便能够分配访问组和访问级别,以满足访问需求表?\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含两个整数$$$n$$$和$$$m$$$($$$1 \\le n, m \\le 500$$$)—开发人员数量和文档数量。\u003c/p\u003e\u003cp\u003e接下来的$$$n$$$行中,每行包含长度为$$$m$$$的二进制字符串—访问需求表。第$$$j$$$行的第$$$i$$$个元素是$$$1$$$,表示第$$$i$$$个开发人员应该访问第$$$j$$$个文档;是$$$0$$$,表示他们不应该访问它。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e第一行应包含一个整数$$$k$$$—Monocarp可以选择的最小访问组数量,以便能够分配访问组和访问级别,以满足访问需求表。\u003c/p\u003e\u003cp\u003e第二行应包含$$$m$$$个整数,从$$$1$$$到$$$k$$$—文档的访问组。\u003c/p\u003e\u003cp\u003e第三行应包含$$$m$$$个整数,从$$$1$$$到$$$10^9$$$—文档的所需访问级别。\u003c/p\u003e\u003cp\u003e接下来的$$$n$$$行中,第$$$i$$$行应包含$$$k$$$个整数,从$$$1$$$到$$$10^9$$$—每个访问组上第$$$i$$$个开发人员的访问级别。\u003c/p\u003e\u003cp\u003e如果有多个解决方案,可以输出任意一个。\u003c/p\u003e"}},{"title":"示例 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2\n01\n11\n10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1 2 \n2 2 \n1 2 \n2 2 \n2 1 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"示例 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 3\n101\n100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1 1 1\n1 10 5\n8\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个示例中,我们将文档分配给不同的访问组。这两份文档在它们的访问组中都有级别$$$2$$$。这样,我们可以为需要访问的开发人员分配级别$$$2$$$,并为必须不访问的开发人员分配级别$$$1$$$。\u003c/p\u003e\u003cp\u003e如果它们属于同一个访问组,就不可能为开发人员$$$1$$$和$$$3$$$分配访问级别。开发人员$$$1$$$在这个组中应该比开发人员$$$3$$$有更低的级别,才不能访问文档$$$1$$$。与此同时,开发人员$$$3$$$在这个组中应该比开发人员$$$1$$$有更低的级别,才不能访问文档$$$2$$$。由于他们两者都不能比对方级别低,所以不可能只有一个访问组。\u003c/p\u003e\u003cp\u003e在第二个示例中,可以将所有文档分配给同一个访问组。\u003c/p\u003e"}}]}