class Solution:
    def twoCitySchedulingCost(self, costs):
        costs.sort(key=lambda li: li[0]-li[1]) #sort回傳None # li[0]-li[1] 以A的機會成本作排列(greddy algorithm)
        expend, countA = 0, 0
        
        #for costA, costB in sorted(costs, key=lambda li: li[0]-li[1]): sorted有回傳
        for costA, costB in costs:
            if countA < len(costs)//2:
                expend += costA
                countA += 1
            else:
                expend += costB
            
        return expend

if __name__ == "__main__":
    costs = [[10,20], [30,200], [400,50], [30,20]]
    costs2 = [[259,770], [448,54], [926,667], [184,139], [840,118], [577,469]]
    print(Solution().twoCitySchedulingCost(costs))
    
class Solution:
    def twoCitySchedulingCost(self, costs):
        costs.sort(key=lambda li: li[0]-li[1]) #sort回傳None # li[0]-li[1] 以A的機會成本作排列(greddy algorithm)
        expend, countA = 0, 0
        
        #for costA, costB in sorted(costs, key=lambda li: li[0]-li[1]): sorted有回傳
        for costA, costB in costs:
            if countA < len(costs)//2:
                expend += costA
                countA += 1
            else:
                expend += costB
            
        return expend

if __name__ == "__main__":
    costs = [[10,20], [30,200], [400,50], [30,20]]
    costs2 = [[259,770], [448,54], [926,667], [184,139], [840,118], [577,469]]
    print(Solution().twoCitySchedulingCost(costs))
    
#sort回傳None # li[0]-li[1] 以A的機會成本作排列(greddy algorithm) #for costA, costB in sorted(costs, key=lambda li: li[0]-li[1]): sorted有回傳