시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB58292251.163%

문제

Dvyniai Antanas ir Bronius gimtadienio proga gavo didelę dėžę sausainių. Iš viso joje yra N skirtingų sausainių, sunumeruotų nuo 1 iki N.

Dvyniams ne visi sausainiai patinka vienodai: i-ąjį sausainį Antanas vertintų ai balų, o Bronius jį vertintų bi balų. Kuo įvertis didesnis, tuo labiau sausainis patinka. Abu dvyniai žino, kiek balų kiekvienas iš jų skirtų kiekvienam sausainiui.

Mama pasiūlė dvyniams saldumynus pasidalinti šitaip: pirmasis vieną sausainį pasirinktų Antanas, paskui iš likusių sausainių vieną pasirinktų Bronius ir taip toliau, iki dėžė ištuštėtų.

Broliai nėra labai draugiški, todėl kiekvienas stengsis rinktis sausainius taip, kad pasibaigus dalyboms jo pasirinktų sausainių įverčių suma būtų kaip įmanoma didesnė už kito brolio pasirinktų sausainių įverčių sumą.

Kitaip tariant, jei dalybų metu Antanas pasirenka sausainius, kuriuos jis įvertina A balų, o Bronius pasirenka sausainius, vertus B balų, tai Antano tikslas yra pasiekti, kad dalybų pabaigoje skirtumas A − B būtų kaip galima didesnis, o Broniaus – kad skirtumas B − A būtų kuo didesnis.

Apskaičiuokite, kam bus lygus skirtumas A−B, jei abu dvyniai sausainius rinksis optimaliai.

입력

Pirmoje eilutėje pateiktas sausainių skaičius N. Toliau eina N eilučių, kurių kiekvienoje pateikta po du sveikuosius skaičius:

  • ai – Antano skiriami balai i-ajam sausainiui;
  • bi – Broniaus skiriami balai i-ajam sausainiui.

출력

Išveskite vieną sveikąjį skaičių – skirtumo A−B reikšmę, jei dvyniai sausainius dalinsis pagal optimalią strategiją.

서브태스크

번호배점제한
18

1 ≤ N ≤ 10, 0 ≤ ai, bi ≤ 1 000

218

1 ≤ N ≤ 22, 0 ≤ ai, bi ≤ 1 000

323

1 ≤ N ≤ 1 000, 0 ≤ ai, bi ≤ 1 000

47

1 ≤ N ≤ 200 000, 0 ≤ ai, bi ≤ 1

514

1 ≤ N ≤ 200 000, 0 ≤ ai, bi ≤ 1 000, ai = bi

630

1 ≤ N ≤ 200 000, 0 ≤ ai, bi ≤ 1 000

예제 입력 1

4
100 1
200 2
400 4
300 3

예제 출력 1

596

Antanas pasirinktų trečią sausainį, Bronius – ketvirtą, tada Antanas – antrą, ir galiausiai Broniui atitektų pirmas.

A = a3 + a2 = 400 + 200 = 600

B = b4 + b1 = 3 + 1 = 4

예제 입력 2

2
10 100
11 50

예제 출력 2

-40

Šiuo atveju Antanas pasirinktų pirmą sausainį, o Broniui atitektų antras.

A = a1 = 10

B = b2 = 50

Jei Antanas būtų pasirinkęs antrą sausainį, A−B būtų lygus a2−b1 = 11−100 = −89, todėl tai nebūtų optimalus Antano pasirinkimas.

채점 및 기타 정보

  • 예제는 채점하지 않는다.