Eventually, Mike gave up with those Nim-like games. He decided to learn how to play “GemCraft” on his own computer. Unfortunately, he could only find the game called “CarCraft” on the internet.

In this game, Mike was given a board with m × n black or white little squares. These little squares formed a special pattern. That is, for each row and each column, the white squares within this single row or column were always connected together. Moreover, when Mike scanned over the board from top to bottom, he discovered that in every row (or column), the beginning position of the white-square segment was always NOT left (or upper) to the beginning position of the upper row (or left column). Also, all the ending positions of the white-square segments were always NOT right (or lower) to the ending position of the lower row (or right column). Mike called this type of board a “CarCarBoard” although there’s another name called “saw-toothed chessboard”.

Here is an example of a “CarCarBoard”:

In “CarCraft”, Mike had to put a banana in his favorite ear to continue the game, but this is not the point. The point is, every little white square must be seen from some Defense Towers in order to keep Fu-Gus away. But this kind of Defense Towers was incredibly expensive. One could buy and build a Tower unless he owned at least three hundred million dollars during the game.

Fortunately, there were some magical abilities provided in the game. Take “Armed Car Mastery” for example. Once the player mastered the skill of “Armed Car Mastery” – ACM in short – he may use K armed cars to prevent Fu-Gus’ appearing. Of course, K was related to the armed level that the player had. All armed cars could be only put on a white square. An armed car could secure all white squares in the same row or same column.

Help Mike calculate the minimum number K such that every white square can be secured when Mike uses at least K armed cars.