We are interested in the cubic-to-tetragonal phase transition in a shape memory alloy. We consider geometrically linear elasticity. In this framework, Dolzmann and Müller have shown that the only stress-free configurations are (locally) twins (i.e. laminates of just two of the three martensitic variants). However, configurations with arbitrarily small elastic energy are not necessarily close to these twins. The formation of a microstructure allows all three martensitic variants to be mixed at arbitrary volume fractions. We take an interfacial energy into account and establish a (local) lower bound on elastic plus interfacial energy in terms of the martensitic volume fractions. The introduction of an interfacial energy introduces a length scale and, thus, together with the linear dimensions of the sample, a non-dimensional parameter. Our lower Ansatz-free bound has optimal scaling in this parameter. It is the scaling predicted by a reduced model introduced and analysed by Kohn and Müller with the purpose of describing the microstructure near an interface between austenite and twinned martensite. The optimal construction features branching of the martensitic twins when approaching this interface.