There are two amazon centers, one in Bangalore and one in Hyderabad where the candidates need to go for interviews. A candidate needs to visit one of the centers and the expense would be on amazon. Each location needs to have half of the candidate(N, candidate number is even) and the cost associated with the travel expense needs to be minimized. Output the cost. Ex: For 6 candidates {20,40}, {10,60}, {5,80}, {60,10}{100,15}, {150,20}. Here lets assume cost is given {Bangalore, Hyderabad} thus first 3 candidates should go to Bangalore and next 3 should go to Hyderabad and total cost is 80.

Please help me out with the most efficient approach. The best I could do is O(n^2) dp solution.