Minimum Cost Pairs