题目描述

有 $N$ 张卡片，每张卡片的两面分别写有一个数字，第 $i$ 张卡片的一面用红色写着 $A_i$，另一面用蓝色写着 $B_i$。一开始，所有卡片都以红色数字朝上摆放。Alice 和 Bob 事先都知道每张牌两面的数字，并进行如下规则的游戏：

• 首先，Alice 从剩下的卡片中选择一张，将其翻面。接着，Bob 从剩下的卡片中选择一张移除。此时，Bob 获得等于该卡片正面数字的分数。

当没有剩余卡片时，游戏结束。

Alice 的目标是让游戏结束时 Bob 的得分最小，Bob 的目标是让自己的得分最大。双方都采取最优策略时，游戏结束时 Bob 的得分是多少？

输入格式

输入按以下格式从标准输入读入。

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\cdots$
$A_N$ $B_N$

输出格式

请输出一个整数，表示答案。

样例 1

输入

3
6 4
2 1
5 3

输出

12

样例 2

输入

5
166971716 552987438
219878198 619875818
918378176 518975015
610749017 285601372
701849287 307601390

输出

3078692091

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$。
• $1 \leq A_i, B_i \leq 10^9$（$1 \leq i \leq N$）。
• 所有输入的值均为整数。

样例解释 1

初始状态下，正面朝上的数字分别为 $6,2,5$。例如，游戏可能按如下方式进行：

1. Alice 翻转第 $1$ 张卡片，此时正面数字变为 $4,2,5$。Bob 移除第 $3$ 张卡片，获得 $5$ 分。
2. Alice 翻转第 $2$ 张卡片，此时正面数字变为 $4,1$。Bob 移除第 $2$ 张卡片，获得 $1$ 分。
3. Alice 翻转最后剩下的第 $1$ 张卡片，此时正面数字变为 $6$。Bob 移除该卡片，获得 $6$ 分。

此时，Bob 的总得分为 $12$。实际上，这是一种双方采取最优策略的流程之一，答案为 $12$。

由 ChatGPT 4.1 翻译