It is clear that minimizing the sum of visible fields is equivalent to maximizing the sum of covered fields. A greedy algorithm ("take the largest domino, delete it, repeat") already fails on the second sample test. Nevertheless, in order to solve this problem, it is sufficient to only observe a certain number of dominoes that are the best or, in other words, largest considering the sum of their fields.

What exactly is that number of dominoes? Let us notice that each domino overlaps with at most ~6~ other dominoes. That means that after taking ~K-1~ dominoes, we've "crossed out" ~7(K-1)~ dominoes in total, so for the last domino it clearly pays off to take one of the best ~7(K-1)+1~ dominoes. Since the order of choosing dominoes is not important, each chosen domino can be the last one, which means that each domino from the optimal choice is one of the best ~7(K-1)+1~ dominoes.

For ~K \le 5~, that number is less than thirty, so trying out every possible combination (from that set of the best dominoes) is quick enough. For ~K \le 8~, the number of dominoes to observe reaches ~50~. Since the number of all possible choices is too large in this case, we will use the meet in the middle approach: we will split the observed set into two parts and, for each of them, observe the possible choices inside it.

Let us first construct a graph where the nodes are dominoes, and two dominoes are connected with an edge if they don't overlap or, in other words, if they can be taken at the same time. Therefore, we need to find a clique (a complete subgraph, i.e. a set of nodes where each two are connected) of size ~K~ where the sum of all the nodes (the dominoes' values) is maximal. Each subgraph is observed as a bitmask, a binary number where ~1~s represent the chosen nodes.

Let us split the graph into two parts so that the first one contains ~A~ nodes and the other ~B~ nodes (sizes ~A~ and ~B~ will be determined later). In all possible ways, let's assume that we will choose ~D~ dominoes of the required clique from the first part and ~K-D~ dominoes from the second part of the graph.

For a fixed ~D~, we do the following:

• In the first part of the graph, for each subgraph ~mask~ we calculate ~dp[mask]~ that gives us the maximal sum of nodes in its subclique of size ~D~.
  • How can we do this? If the subgraph is of size ~D~, we check whether it's a clique, and if it is, we sum up the nodes. If the subgraph consists of more than ~D~ nodes, then $$\displaystyle dp[mask] = \max\{dp[submask]\}$$ for all subgraphs ~submask~ obtained by removing one node (binary ~1~) from the subgraph ~mask~.
• In the second part of the graph, for each clique of size ~K-D~, we search for all the nodes in the first part that are connected to all the nodes from the chosen clique – these nodes from the first part comprise a subgraph ~mask~ and we want to know its best subclique of size ~D~, which is stored in ~dp[mask]~.
• To summarize: for this ~D~, we maximize ~sum(clique)+dp[mask]~ for all cliques in the second part of size ~K-D~ and its corresponding "friendly" subgraphs ~mask~ from the first part.

The final solution is, naturally, the maximum for all ~D = 0, 1, \dots, K~. Finally, how big should the parts ~A~ and ~B~ be? Since in the first part we are observing all subgraphs, and in the second only those of size ~K-D~, the first one should be smaller: in the official solution, ~A = 20~, ~B = 30~. The analysis of this algorithm's complexity is left as an exercise to the reader.