For each piece of metal, find the distance to the closest magnet. In order to pick this piece of metal up, the new magnet must be placed within a certain zone where every square's Manhattan distance is closer than the Manhattan distance to the closest magnet.

If you tilt the coordinate plane ~45~ degrees, this zone looks like a square. If you then draw a checkerboard on the coordinate plane, and look only at the white tiles, it is a square. If you look only at the black tiles, it is also a square.

The intended solution is to do a 2-D line sweep after separating the coordinate plane into two planes, black and white. Out of both planes, the tile which is in the most "zones" is the tile which will pick up the most metal.

Time Complexity: ~\mathcal{O}(NM+4000^2)~