## Rectangle covers Suppose you have a matrix of bits, for example the following. 1 1 0 0 0 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 We would like to find a _rectangle cover_ for this matrix. It is a set of rectangular subsets of the matrix that don't contain any 0s, but together contain all the 1s. The subsets are not required to be disjoint. Here is an example of a rectangle cover for the above matrix. +----+ +----+ |1 1| 0 0 0 |1 1| 0 | | | | | +-|-----+ | |+-+ |1 |1| 1 1| 0 |1 1||1| +----+ | | || | | | | || | 0 |1 1 1| 0 |1 1||1| +-------+ | |+-+ +----+ +-----|-+ | |1 1| 0 |1 1 |1| 1| 0 | | | +----+ | | | | +-+ |1 1| 0 |1 1 1| 0 |1| +----+ +-------+ +-+ The number of rectangles in this cover is 7. ## The task Your input is a rectangular matrix of bits, taken in any reasonable format. You can assume it contains at least one 1. Your output is the minimum number of rectangles in a rectangle cover of the matrix. The lowest byte count wins. Standard [tag:code-golf] rules apply. ## Test cases [[1]] -> 1 [[1,1]] -> 1 [[1],[1]] -> 1 [[1,0,1]] -> 2 [[1,0],[0,0]] -> 1 [[1,0],[0,1]] -> 2 [[1,0],[1,1]] -> 2 [[1,1,1],[1,0,1]] -> 3 [[0,1,0],[1,1,1],[0,1,0]] -> 2 [[1,1,1],[1,0,1],[1,1,1]] -> 4 [[1,1,0],[1,1,1],[0,1,1]] -> 2 [[1,0,1,0],[1,1,1,1],[1,0,1,0]] -> 3 [[1,1,1,0],[1,0,1,0],[1,1,1,1],[0,0,1,0]] -> 4 [[1,1,1,0],[1,0,1,0],[1,1,1,1],[0,0,1,1]] -> 5 [[1,1,1,0],[1,0,1,0],[1,1,1,1],[0,1,1,1]] -> 4 [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]] -> 3 [[0,0,1,0,0],[0,1,1,1,0],[1,1,1,1,1],[0,1,1,1,0],[0,0,1,0,0]] -> 3