P9333 [JOISC 2023] Council (Day2)

In the council of JOI City, there are $N$ assembly members, numbered from $1$ to $N$. The council will open a meeting, and the assembly members will take votes on $M$ proposed ordinances, numbered from $1$ to $M$. If $A_{i, j} = 1$, the assembly member $i \ (1 \le i \le N)$ will cast an affirmative vote on the proposed ordinance $j \ (1 \le j \le M)$. If $A_{i, j} = 0$, the assembly member $i$ will cast a negative vote on the proposed ordinance $j$. The council of JOI City will be performed as follows. 1. Among the $N$ assembly members, they will randomly choose a chairperson by drawing lots. 2. The chairperson will choose a deputy chairperson among the $N - 1$ assembly members except for the chairperson. 3. The votes will be taken on $M$ proposed ordinances. Each of the $N - 2$ assembly members except for the chairperson and the deputy chairperson will cast an affirmative vote or a negative vote on each proposed ordinance. The council will approve a proposed ordinance if a majority of the assembly members (i.e., more than or equal to $\lfloor \frac{N}{2} \rfloor$ assembly members) cast affirmative votes on it. Here, $\lfloor x \rfloor$ is the largest integer not exceeding $x$. Mayor K, the mayor of JOI City, wants the council to approve as many proposed ordinances as possible. Mayor K collected information on assembly members. Mayor K knows, on each proposed ordinance, who will cast an affirmative vote and who will cast a negative vote. Write a program which, given information of the votes of the assembly members, calculates, for each assembly member, the maximum possible number of proposed ordinances approved by the council if that assembly member is chosen as the chairperson.

N/A

N/A

**【样例解释 #1】** - Let’s consider the case where the assembly member $1$ is chosen as the chairperson. If the assembly member $2$ is chosen as the deputy chairperson, the council will approve three proposed ordinances, i.e., the proposed ordinances $1, 2, 3$. If the assembly member $3$ is chosen as the deputy chairperson, the council will approve two proposed ordinances, i.e., the proposed ordinances $1, 2$. Therefore, the maximum number of proposed ordinances approved by the council is $3$. Output $3$ in the first line. - Let’s consider the case where the assembly member $2$ is chosen as the chairperson. If the assembly member $1$ is chosen as the deputy chairperson, the council will approve three proposed ordinances, i.e., the proposed ordinances $1, 2, 3$. If the assembly member $3$ is chosen as the deputy chairperson, the council will approve one proposed ordinance, i.e., the proposed ordinance $1$. Therefore, the maximum number of proposed ordinances approved by the council is $3$. Output $3$ in the second line. - Let’s consider the case where the assembly member $3$ is chosen as the chairperson. If the assembly member $1$ is chosen as the deputy chairperson, the council will approve two proposed ordinances, i.e., the proposed ordinances $1, 2$. If the assembly member $2$ is chosen as the deputy chairperson, the council will approve one proposed ordinance, i.e., the proposed ordinance $1$. Therefore, the maximum number of proposed ordinances approved by the council is $2$. Output $2$ in the third line. 该样例满足子任务 $1, 2, 4, 5, 6, 7$ 的限制。 **【样例解释 #2】** 该样例满足子任务 $1, 2, 5, 6, 7$ 的限制。 **【样例解释 #3】** 该样例满足子任务 $1, 2, 4, 5, 6, 7$ 的限制。 **【样例解释 #4】** 该样例满足所有子任务的限制。 **【数据范围】** 对于所有测试数据，$3 \le N \le 3 \times 10 ^ 5$，$1 \le M \le 20$，$0 \le A_{i, j} \le 1$，保证所有输入均为整数。 |子任务编号|分值|限制| |:-:|:-:|:-:| |$1$|$8$|$N \le 300$| |$2$|$8$|$N \le 3000$| |$3$|$6$|$M \le 2$| |$4$|$19$|$M \le 10$| |$5$|$15$|$M \le 14$| |$6$|$22$|$M \le 17$| |$7$|$22$|无|