{"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 là tập đoàn công nghệ thông tin lớn nhất ở Berland, và Monocarp là trưởng phòng an ninh của công ty. Lần này, anh đối mặt với nhiệm vụ khó khăn nhất từ trước đến nay.\u003c/p\u003e\u003cp\u003eCơ bản, có $$$n$$$ nhà phát triển đang làm việc tại BerSoft, được đánh số từ $$$1$$$ đến $$$n$$$. Có $$$m$$$ tài liệu được chia sẻ trên mạng nội bộ, được đánh số từ $$$1$$$ đến $$$m$$$. Có một bảng yêu cầu truy cập $$$a$$$ sao cho $$$a_{i,j}$$$ (phần tử thứ $$$j$$$ của hàng thứ $$$i$$$) là $$$1$$$ nếu nhà phát triển thứ $$$i$$$ nên được truy cập vào tài liệu thứ $$$j$$$, và là $$$0$$$ nếu họ không được truy cập vào nó.\u003c/p\u003e\u003cp\u003eĐể hạn chế quyền truy cập, Monocarp sẽ thực hiện các hành động sau:\u003c/p\u003e\u003cul\u003e \u003cli\u003e chọn số nhóm truy cập $$$k \\ge 1$$$; \u003c/li\u003e\u003cli\u003e gán cho mỗi tài liệu một nhóm truy cập (một số nguyên từ $$$1$$$ đến $$$k$$$) và cấp độ truy cập yêu cầu (một số nguyên từ $$$1$$$ đến $$$10^9$$$); \u003c/li\u003e\u003cli\u003e gán cho mỗi nhà phát triển $$$k$$$ giá trị số nguyên (từ $$$1$$$ đến $$$10^9$$$) — cấp độ truy cập của họ cho mỗi nhóm truy cập. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eNhà phát triển $$$i$$$ có quyền truy cập vào tài liệu $$$j$$$ nếu cấp độ truy cập của họ cho nhóm truy cập của tài liệu lớn hơn hoặc bằng cấp độ truy cập yêu cầu của tài liệu.\u003c/p\u003e\u003cp\u003eSố nhỏ nhất nhóm truy cập mà Monocarp có thể chọn để có thể gán nhóm truy cập và cấp độ truy cập để thỏa mãn bảng yêu cầu truy cập là bao nhiêu?\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa hai số nguyên $$$n$$$ và $$$m$$$ ($$$1 \\le n, m \\le 500$$$) — số nhà phát triển và số tài liệu.\u003c/p\u003e\u003cp\u003eMỗi trong $$$n$$$ dòng tiếp theo chứa một chuỗi nhị phân có độ dài $$$m$$$ — bảng yêu cầu truy cập. Phần tử thứ $$$j$$$ của hàng thứ $$$i$$$ là $$$1$$$ nếu nhà phát triển thứ $$$i$$$ nên được truy cập vào tài liệu thứ $$$j$$$, và là $$$0$$$ nếu họ không được truy cập vào nó.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên nên chứa một số nguyên $$$k$$$ — số nhỏ nhất nhóm truy cập mà Monocarp có thể chọn để có thể gán nhóm truy cập và cấp độ truy cập để thỏa mãn bảng yêu cầu truy cập.\u003c/p\u003e\u003cp\u003eDòng thứ hai nên chứa $$$m$$$ số nguyên từ $$$1$$$ đến $$$k$$$ — các nhóm truy cập của các tài liệu.\u003c/p\u003e\u003cp\u003eDòng thứ ba nên chứa $$$m$$$ số nguyên từ $$$1$$$ đến $$$10^9$$$ — các cấp độ truy cập yêu cầu của các tài liệu.\u003c/p\u003e\u003cp\u003eDòng thứ $$$i$$$ của $$$n$$$ dòng tiếp theo nên chứa $$$k$$$ số nguyên từ $$$1$$$ đến $$$10^9$$$ — cấp độ truy cập của nhà phát triển thứ $$$i$$$ trên mỗi nhóm truy cập.\u003c/p\u003e\u003cp\u003eNếu có nhiều giải pháp, in bất kỳ giải pháp nào.\u003c/p\u003e"}},{"title":"Ví dụ","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":"","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":"Ghi chú","value":{"format":"HTML","content":"\u003cp\u003eTrong ví dụ đầu tiên, chúng ta gán các tài liệu vào các nhóm truy cập khác nhau. Cả hai tài liệu đều có cấp độ $$$2$$$ trong nhóm truy cập của chúng. Như vậy, chúng ta có thể gán cho các nhà phát triển, cần truy cập, cấp độ $$$2$$$, và các nhà phát triển, phải không được truy cập, cấp độ $$$1$$$.\u003c/p\u003e\u003cp\u003eNếu chúng có cùng nhóm truy cập, sẽ không thể gán cấp độ truy cập cho nhà phát triển $$$1$$$ và $$$3$$$. Nhà phát triển $$$1$$$ nên có cấp độ thấp hơn nhà phát triển $$$3$$$ trong nhóm này để không thể truy cập vào tài liệu $$$1$$$. Đồng thời, nhà phát triển $$$3$$$ nên có cấp độ thấp hơn nhà phát triển $$$1$$$ trong nhóm này để không thể truy cập vào tài liệu $$$2$$$. Vì họ không thể cùng có cấp độ thấp hơn nhau, không thể chỉ có một nhóm truy cập.\u003c/p\u003e\u003cp\u003eTrong ví dụ thứ hai, có thể gán tất cả các tài liệu vào cùng một nhóm truy cập.\u003c/p\u003e"}}]}