Branch selection is a key decision in a cadet's military career. Cadets at USMA can increase their branch priorities at a fraction of slots by extending their service agreement. This real‐life matching problem fills an important gap in the market design literature, providing strong empirical legitimacy to a series of elegant theoretical works on matching with contracts. Although priorities fail a key substitutes condition, the agent‐optimal stable mechanism is well defined, and in contrast to the current USMA mechanism it is fair, stable, strategy‐proof, and respects improvements in cadet priorities. Adoption of this mechanism benefits cadets and the Army. This new application shows that the matching with contracts model is practically relevant beyond traditional domains that satisfy the substitutes condition.