hanzch   1년 전

Sausainiai

시간 제한 메모리 제한
1 초 1024 MB

문제

쌍둥이 Antanas와 Bronius는 생일 선물로 큰 쿠키 상자를 받았습니다. 상자에는 총 N개의 서로 다른 쿠키가 있으며, 1부터 N까지 번호가 매겨져 있습니다.

쌍둥이들은 모든 쿠키를 똑같이 좋아하지는 않습니다: Antanas는 i번째 쿠키에 ai점을 부여하고, Bronius는 bi점을 부여합니다. 점수가 높을수록 쿠키를 더 좋아합니다. 두 쌍둥이 모두 각자가 각 쿠키에 부여하는 점수를 알고 있습니다.

엄마는 쌍둥이들에게 다음과 같이 과자를 나누도록 제안했습니다: 먼저 Antanas가 한 쿠키를 선택하고, 그 다음 남은 쿠키 중에서 Bronius가 하나를 선택하고, 이런 식으로 상자가 비워질 때까지 계속합니다.

형제들은 그다지 우호적이지 않기 때문에, 각자는 나눔이 끝났을 때 자신이 선택한 쿠키의 점수 합이 형제의 쿠키 점수 합보다 가능한 한 크게 되도록 쿠키를 선택하려고 합니다.

다시 말해, 나눔 과정에서 Antanas가 선택한 쿠키들의 점수 합을 A, Bronius가 선택한 쿠키들의 점수 합을 B라고 할 때, Antanas의 목표는 나눔이 끝날 때 A - B의 차이를 가능한 크게 만드는 것이고, Bronius의 목표는 B - A의 차이를 가능한 크게 만드는 것입니다.

두 쌍둥이가 최적으로 쿠키를 선택할 때, A-B의 차이가 얼마인지 계산하세요.

입력

첫 번째 줄에는 쿠키의 개수 N이 주어집니다. 그 다음 N개의 줄에는 각각 두 개의 정수가 주어집니다:

  • ai - Antanas가 i번째 쿠키에 부여하는 점수;
  • bi - Bronius가 i번째 쿠키에 부여하는 점수;

출력

하나의 정수를 출력하세요 - 쌍둥이들이 최적의 전략으로 쿠키를 나눌 때 A-B의 값을 출력하세요.

서브태스크

번호 배점 제한
1 8 1 ≤ N ≤ 10, 0 ≤ ai, bi ≤ 1 000
2 18 1 ≤ N ≤ 22, 0 ≤ ai, bi ≤ 1 000
3 23 1 ≤ N ≤ 1 000, 0 ≤ ai, bi ≤ 1 000
4 7 1 ≤ N ≤ 200 000, 0 ≤ ai, bi ≤ 1
5 14 1 ≤ N ≤ 200 000, 0 ≤ ai, bi ≤ 1 000, ai = bi
6 30 1 ≤ N ≤ 200 000, 0 ≤ ai, bi ≤ 1 000

예제 입력 1

4
100 1
200 2
400 4
300 3
596

Antanas는 세 번째 쿠키를 선택하고, Bronius는 네 번째 쿠키를 선택한 다음, Antanas는 두 번째 쿠키를 선택하고, 마지막으로 Bronius에게 첫 번째 쿠키가 돌아갑니다.
A = a3 + a2 = 400 + 200 = 600
B = b4 + b1 = 3 + 1 = 4

예제 입력 2

2
10 100
11 50
-40

이 경우 Antanas는 첫 번째 쿠키를 선택하고, Bronius에게는 두 번째 쿠키가 돌아갑니다.
A = a1 = 10
B = b2 = 50
만약 Antanas가 두 번째 쿠키를 선택했다면, A-B는 a2-b1 = 11-100 = -89가 되었을 것이므로, 이는 Antanas에게 최적의 선택이 아닙니다.

댓글을 작성하려면 로그인해야 합니다.