In order to score points on the first subtask, it was enough to note that, due to the small number of ones, the number of questions in our crossword puzzle is very small. It was enough to use brute force in order to traverse each subset of those questions and assume that was the subset of questions that needed to be answered. For each subset, we check whether the crossword puzzle was filled. The time complexity is ~\mathcal O(2^Q NM)~, where ~Q~ denotes the total number of questions.

The constraints of the second subtask will immediately put an experienced contestant on the right track. One dimension of the matrix is very small and the problem immediately starts smelling like dynamic programming with bitmasks. And that intuition is correct, we will traverse the matrix row-by-row and store in our bitmask in which columns we have decided to answer vertical questions whose answers span through the current row. Therefore, the state can be denoted with ~dp[row][mask]~ and it tells us what is the minimal number of questions that need to be answered in order to fill an entire crossword puzzle if we have filled all rows until ~row-1~ and we are currently at row ~row~ with ~mask~ storing active columns as described. Further analysis of the transitions and the reconstruction are left as an exercise to the reader.

Sometimes it is useful to obtain a more formal description of the problem. In this case, that will naturally lead us to the full solution. Let's denote the horizontal questions with ~a_1, a_2, \dots, a_p~, and vertical questions with ~b_1, b_2, \dots, b_q~. Let ~a_i~ (or ~b_j~) be equal to ~1~ if we choose to answer that particular question in our solution and ~0~ otherwise. Note that for each empty square ~x~ we need to choose to answer at least one of exactly two questions which have answers that contain ~x~. Therefore, for each empty square there are exactly two questions ~a_i~ and ~b_j~ for which ~a_i \lor b_j = 1~ must hold.

Let's model this with a bipartite graph in which on one side we have nodes that represent horizontal questions, and on the other side we have nodes that represent vertical questions. Let's connect two nodes that represent questions ~a_i~ and ~b_j~ with an edge if there exists an empty square for which ~a_i \lor b_j = 1~ must hold. Now, we want to determine the smallest subset of nodes such that each edge is incident to at least one node from that subset. This is a famous problem called minimum vertex cover. Since the graph is bipartite, we can use Kőnig's theorem and solve the problem in polynomial complexity.