Two-City Onsite Flight Cost Minimization

You are given n candidates attending an onsite. For each candidate i, the cost to fly to New York is c1[i] and the cost to fly to San Francisco is c2[i]. Constraints: Exactly half of the candidates must fly to New York and the other half to San Francisco. If n is odd, the number flying to New York is ceil(n/2) and the number flying to San Francisco is floor(n/2). Return the minimum possible total cost while satisfying the headcount constraint. Input An integer n Two arrays c1 and c2 of length n Output An integer: the minimum total cost Typical constraints 1 <= n <= 1e5 0 <= c1[i], c2[i] <= 1e9 Sample tests (5) n=4, c1=[10,20,30,40], c2=[100,50,20,10] → 60 n=1, c1=[5], c2=[100] → 5 n=3, c1=[10,10,10], c2=[1,2,3] → 14 n=2, c1=[1,100], c2=[100,1] → 2 n=5, c1=[8,7,6,5,4], c2=[1,2,3,4,5] → 20 Example Input 4 10 20 30 40 100 50 20 10 Output 60