Let's observe the board:

xxooxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx

Let's separate black and white cells (one bishop always jumps by white cells, and the other by black cells):

 x o x    x o x
x x x      x x x
 x x x    x x x
x x x      x x x
 x x x    x x x
x x x      x x x

Let's rotate the board by ~45^\circ~:

  xx        x
 xxxo      xxo
xxxxxx    xxxxx
 xxxx     xxxxx
  xx       xxx
            x

We can sort rows by length, by which the same set of cells will still be visible from every cell:

xxxxxx    xxxxx
 xxxx     xxxxx
 xxxo      xxx
  xx       xxo
  xx        x
            x

Same is applied to columns:

xxxxxx    xxxxx
xxxx      xxxxx
xxxo      xxx
xx        xxo
xx        x
          x

Now, we have to solve the upper left sorted board. I.e. for every ~K~, what is the optimal solution if bishops make ~K~ steps on the board?

Let's take a look at ~R~ rows and ~C~ columns in which a bishop will show at least once. It is certain that the first row from ~R~ has to cut with the last column from ~C~ (in other words, the last column isn't intersecting with anyone, so it can't be visited). It is certain that the last row from ~R~ has to cut with the first column from ~C~ (in other words, the last row isn't intersecting with anyone, so it can't be visited).

If those assumptions are true, then the first row from ~R~ is intersecting with every column from ~S~. Then it is possible to make these jumps (which will jump into every row and every column exactly once):

1. Jump from starting row to first for in ~R~.
2. Jump to every column from ~S~ in any order, but in the end, jump to the first column in ~S~ (first row from ~R~ can see every column from ~S~).
3. Jump to every other row from ~R~ (first row from ~S~ can see every row from ~R~).

It can be seen that a bishop has to jump to the same column in step 2 twice (if starting column is the first one from ~S~). So, if starting column is the first column from ~S~, then the bishop won't jump in not even one other column and step 2 can be thrown out.

Further: For ~k = 0~, it is necessary to outtake starting cell of bishop because it doesn't count. For ~k \ge 2~, it is possible to decide to jump only by already seen rows/columns, so it is necessary to do ~dp[k] = \max(dp[k-1], dp[k])~.

Implementation:

1. Choose a subset of columns that contains the starting column of bishop in every way. For every row calculate how many points is there left.
2. Choose the best row from which bishop can jump to every column in subset.
3. Choose the starting row.
4. From now on, we add one by one the best row in which bishop can jump from first column from subset. (Curator's note: This grammar sucks. Feel free to open a ticket.)

For ~100\%~ points, it is necessary to conclude that it is never good to jump in any corner, so a step in which every subset is chosen can evaluate ~4~ times faster. Without this optimization, ~90\%~ points can be achieved.