AT_nikkei2019_qual_c Different Strokes

高桥君和青木小姐面前有 $N$ 盘菜。为了方便起见，这些菜分别称为菜 $1$、菜 $2$、……、菜 $N$。 高桥君吃第 $i$ 盘菜时会获得 $A_i$ 点的“幸福度”。同样，青木小姐吃第 $i$ 盘菜时会获得 $B_i$ 点的幸福度。 他们从高桥君开始，轮流选择一盘菜吃，直到所有菜都被吃完。并且，他们都会以“最大化自己最终获得的幸福度总和减去对方最终获得的幸福度总和”为目标来选择菜。 请问，“高桥君最终获得的幸福度总和”减去“青木小姐最终获得的幸福度总和”是多少？

输入以如下格式从标准输入给出。 > $N$ > $A_1$ $B_1$ > $A_2$ $B_2$ > $\vdots$ > $A_N$ $B_N$

输出“高桥君最终获得的幸福度总和”减去“青木小姐最终获得的幸福度总和”的值。

## 限制条件 - $1 \leq N \leq 10^5$ - $1 \leq A_i \leq 10^9$ - $1 \leq B_i \leq 10^9$ - 输入的所有值均为整数。 ## 样例解释 1 在这个例子中，无论两人谁吃第 $1$ 盘菜都能获得 $10$ 点幸福度，吃第 $2$ 盘菜获得 $20$ 点幸福度，吃第 $3$ 盘菜获得 $30$ 点幸福度。由于两人的“偏好”完全一致，他们每次都会选择剩下的菜中能获得最多幸福度的那一盘。因此，首先高桥君会选择第 $3$ 盘菜，然后青木小姐选择第 $2$ 盘菜，最后高桥君选择第 $1$ 盘菜，所以答案为 $(30 + 10) - 20 = 20$。 ## 样例解释 2 在这个例子中，高桥君无论吃第 $1,2,3$ 盘菜都能获得 $20$ 点幸福度，但青木小姐吃第 $1$ 盘菜获得 $10$ 点幸福度，吃第 $2$ 盘菜获得 $20$ 点幸福度，吃第 $3$ 盘菜获得 $30$ 点幸福度。这次只有青木小姐有偏好，因此他们每次都会选择剩下的菜中青木小姐能获得最多幸福度的那一盘。因此，首先高桥君会选择第 $3$ 盘菜，然后青木小姐选择第 $2$ 盘菜，最后高桥君选择第 $1$ 盘菜，所以答案为 $(20 + 20) - 20 = 20$。 ## 样例解释 3 答案可能不会落在 $32$ 位整数范围内。 由 ChatGPT 4.1 翻译