Given M one-by-one tiles and N two-by-two tiles, what's the largest side-length of a square that you can make if the square must be completely filled in the middle?

I was recently asked this problem in an interview, and I came up with an incorrect dynamic programming approach. I did some sort of three-state DP with (m, n, k), where k is the current square side-length. From (m, n, k), we can transition to a state with k' = k + 1 by using some number of one-by-one tiles (around the border of the current square with side-length k), and we can transition to a state with k' = k + 2 by using some number of two-by-two tiles.

However, this is clearly not exhaustive: It doesn't take into account when we can use a combination of both tiles.

I think this might be purely a combinatorial problem. Could someone please help me with the right approach? Even after thinking for a few more days, I can't come up with a solution.