====== Cards ======

===== 풀이 =====
  * 각 카드를 +로 쓸지 -로 쓸지, 둘 중의 한가지 값을 결정해줘야 한다. 그런데 +로 써야 하는 카드의 수가 정해져있다.
  * 이것은 흔히 보이는 그리디 유형이다. 각 원소들을 A와 B중 하나로 결정해서 점수 합이 최대가 되도록 하는 문제인데, 각 원소들을 {A로 쓸 때의 점수} - {B로 쓸 때의 점수} 기준으로 정렬해서 상위 N개를 A로 사용하는 것이 최적이 된다.
  * 여기에서는 총합을 가장 작게 만드는 것이 목표니까. 카드들 중에서 {+로 쓸때 최솟값} - {-로 쓸때 최솟값} 이 가장 큰 N개를 +로 써야 한다.
  * 식을 정리하면 재밌어지는데, +로 쓸때의 최솟값은 min(a,b) 이고, -로 쓸때의 최솟값은 -max(a,b) 이므로, 저 식에 대입하면 min(a,b) - (-max(a,b)) = a+b가 된다.
  * 결국, a+b를 기준으로 정렬해서 작은쪽 절반은 min(a,b)를, 큰쪽 절반은 -max(a,b)를 취하면 된다.
  * 시간복잡도는 정렬에 필요한 O(nlogn)에 바운드된다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 3373. Cards".

- Problem link: https://www.acmicpc.net/problem/3373
- Solution link: http://www.teferi.net/ps/problems/boj/3373

Tags: [greedy]
"""

import sys


def main():
    N = int(sys.stdin.readline())  # pylint: disable=unused-variable
    a_and_b = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    a_and_b.sort(key=sum)
    answer = sum(min(t) for t in a_and_b[: N // 2]) - sum(
        max(t) for t in a_and_b[N // 2 :]
    )

    print(answer)


if __name__ == '__main__':
    main()

</dkpr>

{{tag>BOJ ps:problems:boj:골드_3}}