Sausainiai
시간 제한1초메모리 제한1024 MB
두 사람이 번갈아 쿠키를 하나씩 가져가며 각자 자신의 점수 합에서 상대 점수 합을 뺀 값이 최대가 되도록 선택할 때, 최적으로 나눈 뒤의 차이 A-B를 구한다.
문제
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ą.