ISL 2009 C4

For an integer $m \geq 1$, we consider partitions of a $2^{m} \times 2^{m}$ chessboard into rectangles consisting of cells of the chessboard, in which each of the $2^{m}$ cells along one diagonal forms a separate rectangle of side length 1 . Determine the smallest possible sum of rectangle perimeters in such a partition.