Note that the condition on good grids is equivalent to every ~2~ by ~2~ subgrid having ~2~ occurrences of one letter and ~1~ occurrence each of the other two letters, and the ~2~ equal letters must be adjacent to each other.

For an ~N~ by ~M~ good grid of square cells, consider the ~N+1~ by ~M+1~ grid of vertices and edges that surround the cells. Let's bold an edge in this grid if it is not a boundary edge and the two cells that touch it have the same letter, as shown below:

Observe that the condition implies that these bolded edges form a matching in this ~N+1~ by ~M+1~ grid graph. Furthermore, all ~(N-1)(M-1)~ inner vertices must be matched, and all boundary edges are not in the matching. It is now natural to conjecture that any such matching corresponds to a good grid, which we will prove when constructing the actual good grid later.

We can initialize the weight of all these edges to ~0~, and for each of the ~K~ constraints, add ~a_i~ to the edge between ~(x_{1i},y_{1i})~ and ~(x_{2i},y_{2i})~. Then we need to find a maximum weight matching that satisfies the conditions. To do this, we can build a min cost max flow network similar to the network used for finding a maximum weight matching in a bipartite graph. There are many ways to do this, differing in how the boundary vertices/edges are handled. For example:

• We reduce the problem to finding a maximum weight perfect matching in a bipartite graph. Colour the vertices of the inner ~N-1~ by ~M-1~ grid black and white in a checkerboard pattern (say, the top-left vertex is white). In addition to the weighted edges that connect two adjacent vertices, we add an edge between each black vertex ~u~ and white vertex ~v~ on the perimeter of the inner ~N-1~ by ~M-1~ grid with weight equal to the sum of the weights of the edges that connect ~u~ or ~v~ to the perimeter of the ~N+1~ by ~M+1~ grid. If ~u~ and/or ~v~ is a corner vertex, we only take the maximum such weight. Finally, if ~(N-1)(M-1)~ is odd, we add another black vertex and connect it to all boundary white vertices ~v~, with weight equal to the weight of ~v~'s perimeter-touching edge. Now any perfect matching in this bipartite graph corresponds to a valid matching as needed.
• Based on the solution above, instead of adding an edge between all pairs of differently coloured boundary vertices, consider the min cost max flow network formed by the weighted bipartite graph of the inner ~N-1~ by ~M-1~ grid. We add an extra vertex ~x~ to this graph, and connect all left side boundary vertices ~u~ with ~x~ with capacity ~1~ and cost equal to the negative of the weight of ~u~'s perimeter-touching edge. Similarly, we connect ~x~ to all right side boundary vertices ~v~ with capacity ~1~ and cost equal to the negative of the weight of ~v~'s perimeter-touching edge. If ~(N-1)(M-1)~ is odd, we add another node to the smaller side and connect it with ~x~ with capacity ~1~ and cost ~0~, as well as to the source or sink. Now any max flow in this graph corresponds to a valid matching as needed, and this solution requires slightly fewer edges than the solution above.
• Finally, we can model the conditions directly using flows with lower bounds. We can build the usual maximum weight matching min cost max flow network from the entire ~N+1~ by ~M+1~ grid and force all inner vertices to be matched with a lower bound of ~1~ on the edge that connects it to the source or sink. Then, we can reduce this network to one without lower bounds (see cp-algorithms for more details) and run a min cost max flow algorithm on it.

All of these solutions need ~\mathcal{O}(NM)~ nodes and edges in the min cost max flow graph, and the max flow is ~\mathcal{O}(NM)~ as well. Using Ford-Fulkerson with potentials so that we can use Dijkstra to find the shortest augmenting path in each iteration, we can find the answer to the problem in ~\mathcal{O}(N^2M^2\log(NM))~. For more details, check out this Codeforces tutorial.

Remark: It is possible to make min cost max flow algorithms that use SPFA run in its worst case ~\mathcal{O}(N^3M^3)~ time with a test case that includes a long path with weights ~\dots, 10^9-16, 10^9-9, 10^9-4, 10^9-1, 10^9, 10^9-1, 10^9-4, 10^9-9, 10^9-16, \dots~ through the inner grid graph.

To construct the good grid from the matching, consider drawing an arrow between any two adjacent cells pointing right or down. Label each arrow with a ~1~ or a ~2~ in an alternating pattern as shown below:

Now for each matched edge, replace the corresponding arrow's weight with a ~0~:

Observe that since the matching satisfies the conditions, for any ~2~ by ~2~ subgrid, the right-down path and the down-right path from its top-left cell to the bottom-right cell have the same sum of labels modulo ~3~. It follows that for each cell, all paths from the top-left corner to it have the same sum of labels modulo ~3~. We can assign a letter A, B, or C to this cell depending on this value modulo ~3~, and we can easily verify that this gives a good grid as required.

Another way to construct the good grid is to set the top-left ~2~ by ~2~ cells to be anything that satisfies the condition within this subgrid and repeatedly fill in the other cells when it can be uniquely determined from the current information (e.g. with a queue of cells to check). Any time we run out of uniquely determinable cells, it can be shown that we must have filled in all the rows up to some point where the last row's cells are all filled in the same letter or similarly for columns. It suffices to fill in any of the two options for a cell adjacent to the filled-in region and continue until we filled in the entire grid. Assuming that a good grid exists from any matching, we can see that this algorithm works.

Time complexity: ~\mathcal{O}(K+N^2M^2\log(NM))~