Chef and Rectangle Genome

Chef has an empty matrix of NxM. He wants to construct rectangle genome. For this reason Chef should fill the matrix with letters G, С, A, T. The genome will be stable if it contains K different submatrices. Of course, Chef wants to make his genome as stable as possible, that is the difference between the number of different submatrices in genome and number K should be as small as possible. Plea