Inertia-dominated mechanical systems can achieve net displacement by 1) periodically changing their shape (known as kinematic gait) and 2) adjusting their inertia distribution to utilize the existing nonzero net momentum (known as momentum gait). Therefore, finding the gait that most effectively utilizes the two types of locomotion in terms of the magnitude of the net momentum is a significant topic in the study of locomotion. For kinematic locomotion with zero net momentum, the geometry of optimal gaits is expressed as the equilibria of system constraint curvature flux through the surface bounded by the gait, and the cost associated with executing the gait in the metric space. In this paper, we identify the geometry of optimal gaits with nonzero net momentum effects by lifting the gait description to a time-parameterized curve in shape-time space. We also propose the variational gait optimization algorithm corresponding to the lifted geometric structure, and identify two distinct patterns in the optimal motion, determined by whether or not the kinematic and momentum gaits are concentric. The examples of systems with and without fluid-added mass demonstrate that the proposed algorithm can efficiently solve forward and turning locomotion gaits in the presence of nonzero net momentum. At any given momentum and effort limit, the proposed optimal gait that takes into account both momentum and kinematic effects outperforms the reference gaits that each only considers one of these effects.