Think about first sorting the pairs by cost.