{"problem":{"name":"Reversible Card Game","description":{"content":"There are $N$ cards, each with a number written on both sides. On the $i$\\-th card, the number $A_i$ is written in red on one side, and the number $B_i$ is written in blue on the other side. Initially","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc164_c"},"statements":[{"statement_type":"Markdown","content":"There are $N$ cards, each with a number written on both sides. On the $i$\\-th card, the number $A_i$ is written in red on one side, and the number $B_i$ is written in blue on the other side. Initially, all cards are placed with the red number side facing up. Alice and Bob play a game in which they repeat the following steps.\n\n*   First, Alice chooses one of the remaining cards and flips it over. Next, Bob removes one of the remaining cards. Then, Bob scores points equal to the number written on the face-up side of the removed card.\n\nThe game ends when there are no cards left.\nAlice tries to minimize Bob's score at the end of the game, and Bob tries to maximize it. What is Bob's score at the end of the game when both players take optimal steps?\n\n## Constraints\n\n*   $1\\leq N\\leq 2\\times 10^5$\n*   $1\\leq A_i, B_i\\leq 10^9$ $(1\\leq i \\leq N)$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_N$ $B_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc164_c","tags":[],"sample_group":[["3\n6 4\n2 1\n5 3","12\n\nIn the initial state, the numbers written on the face-up sides are $6,2,5$. One possible progression from here is as follows.\n\n1.  Alice flips the first card. Then, the numbers written on the face-up sides are $4,2,5$. Bob removes the third card and scores $5$ points.\n2.  Alice flips the second card. Then, the numbers written on the face-up sides are $4,1$. Bob removes the second card and scores $1$ point.\n3.  Alice flips the first card, the final one remaining. Then, the number written on the face-up side is $6$. Bob removes it and scores $6$ points.\n\nIn this case, Bob's final score is $12$ points. In fact, this progression is an example of optimal sequences of moves for both players; the answer is $12$."],["5\n166971716 552987438\n219878198 619875818\n918378176 518975015\n610749017 285601372\n701849287 307601390","3078692091"]],"created_at":"2026-03-03 11:01:13"}}