해적과 보물
시간 제한1초메모리 제한256 MB
두 사람이 가치 평가가 다른 보물 상자를 번갈아 가져갈 때, 양쪽이 최선을 다한 결과 얻는 점수 차이를 구한다.
문제
해적 Alice와 Bob은 최근 보물섬에서 엄청난 양의 보물을 발견했다. 두 사람은 보물 상자 N개를 발견했고, 공평하게 번갈아가며 상자를 하나씩 골라 나눠 갖기로 했다. 각 상자의 가치는 사람마다 다르게 매길 수 있으므로, 두 사람은 자신이 생각하는 가치를 적어 서로에게 공개했다. 즉 i번째 상자는 Alice에게 A[i] 달러, Bob에게 B[i] 달러의 가치가 있다.
상자를 나눠 갖기 위해 Alice부터 시작해서 Alice와 Bob이 번갈아가며 남은 상자 중 하나를 가져간다. 상자를 하나 가져가면 상대방의 차례이며, N개의 상자가 모두 주인을 찾으면 두 사람은 각자 갈 길을 떠난다.
상자를 모두 나눈 후 Alice가 가져간 상자의 (Alice 기준) 가치 총합을 ScoreA, Bob이 가져간 상자의 (Bob 기준) 가치 총합을 ScoreB라 하자. 두 사람은 약속을 지키는 의리 있는 해적이지만 욕심이 많아서, Alice는 (ScoreA - ScoreB)를 최대로 만들도록 상자를 고르고 Bob은 (ScoreB - ScoreA)를 최대로 만들도록 상자를 고른다.
두 사람은 언제나 최선을 다해 어떤 상자를 가져갈지 결정한다.
예를 들어 N = 3이고 세 상자의 가치가 다음과 같다고 하자.
- 상자 1: A[1] = 10, B[1] = 5
- 상자 2: A[2] = 100, B[2] = 90
- 상자 3: A[3] = 2, B[3] = 0
Alice가 상자 2를 먼저 가져가고, Bob이 상자 1을 가져가고, 마지막으로 Alice가 상자 3을 가져가면 Alice는 102달러, Bob은 5달러어치를 가져간다. Alice가 첫 차례에 상자 2 대신 다른 상자(상자 1 또는 상자 3)를 가져가면 Bob이 자기 차례에 상자 2를 가져가므로, 이 경우 Alice는 10+2 = 12달러, Bob은 90달러어치를 가져간다. 따라서 Alice가 최선을 다하면 첫 차례에 반드시 상자 2를 가져가야 한다.
보물 상자의 수 N과 두 해적이 각자 생각하는 상자의 가치가 주어졌을 때, 두 사람이 최선을 다해 각자의 목표를 최대화했을 때의 (ScoreA - ScoreB) 값을 구하는 프로그램을 작성하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 줄에는 정수 N이 주어지며, 이는 보물 상자의 수다.
다음 N줄에 걸쳐 각 상자의 가치가 공백으로 구분되어 주어진다. 첫 수는 Alice가 생각하는 가치, 두 번째 수는 Bob이 생각하는 가치다.
출력
각 테스트 케이스에 대하여 두 사람이 최선을 다해 게임을 플레이했을 때의 (ScoreA - ScoreB) 값을 출력한다.
제한
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100,000
- 0 ≤ A[i], B[i] ≤ 100,000