조종사 배정
시간 제한1초메모리 제한128 MB
나이순으로 정렬된 조종사들을 대상으로 선장이 항상 부조종사보다 나이가 많도록 짝지어 총 급여를 최소화하는 문제입니다.
문제
찰리는 항공 운송 회사를 운영하고 있다. 회사에는 N명의 조종사가 있으며, N은 짝수이다. 찰리는 정확히 N/2개의 승무원 조를 만들어야 한다.
각 조는 기장 1명과 부기장 1명으로 이루어진다. 기장은 반드시 부기장보다 나이가 많아야 한다.
각 조종사의 계약에는 기장으로 일할 때의 급여 X_i와 부기장으로 일할 때의 급여 Y_i가 정해져 있다. 같은 조종사에 대해서는 항상 기장 급여가 부기장 급여보다 크다. 다만 한 조 안에서 부기장의 급여가 그 조의 기장 급여보다 클 수는 있다.
모든 조종사에게 유효한 역할을 하나씩 배정해 조를 만들 때, 회사가 지급해야 하는 급여 총액의 최솟값을 구하라.
입력
첫째 줄에 조종사의 수를 나타내는 짝수 N (2 <= N <= 10000)이 주어진다.
다음 N개의 줄에는 각 조종사의 급여를 나타내는 두 정수 X_i와 Y_i (1 <= Y_i < X_i <= 100000)가 주어진다. X_i는 그 조종사가 기장으로 일할 때의 급여이고, Y_i는 부기장으로 일할 때의 급여이다.
조종사는 나이가 어린 순서부터 나이가 많은 순서로 주어진다.
출력
모든 조를 만들기 위해 필요한 급여 총액의 최솟값을 정수 하나로 출력한다.