import java.util.Arrays;
public class MianShi {
    /**
     * 今天有N个面试者需要面试，公司安排了两个面试的城市A和B，每一个面试者都有到A城市的开销costA和到B城市的开销costB。
     * 公司需要将面试者均分成两拨，使得total cost最小。 说明：题目要求去A的人数和去B的人数相等。 样例： 输入: cost =
     * [[5,4],[3,6],[1,8],[3,9]] 输出: 14 说明: 第一个和第二个人去B城市，剩下的去A城市
     */
    //#8月19
    public int mianshi(int[][] cost, int n) {
        int totalcost = 0;
        int[] diff = new int[n];
        /**
         * 贪心原则 每个面试cost 每个面试者去cost 最小的 4+3+1+3 = 11,这个肯定不对 因为要求 A B 是均等的 人数一样。
         * 要求 n/2*costA+n/2*costB 最小 
         * n/2*costA+n/2*costB= n/2(costA+CostB)=n/2(CostA+CostA+CostB-CostA)= n*CostA + n/2(CostB-CostA) 只要 按照
         * CostB-CostA 贪心思想：这个差值从小到大排序即可，取前 N/2 个
         */
        for (int i = 0; i < n; i++) {
            totalcost += cost[i][0];
            diff[i] = cost[i][1] - cost[i][0];
        }
        Arrays.sort(diff);
        for (int j = 0; j < n / 2; j++) {
            totalcost += diff[j];
        }
        return totalcost;
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        int[][] cost = new int[][]{{5,4},{3,6},{1,8},{3,9}};
        System.out.println(new MianShi().mianshi(cost, 4));
    }
}