제271회 웰노운컵

2250년, 전 세계가 기다려 온 웰노운컵 제271회 대회가 열린다. 2018년에 1회가 열렸을 때는 "웰노운 알고리즘으로 풀 수 있는 문제들"이라는 뜻에서 웰노운컵이라는 이름이 붙었지만, 지금은 출제와 검수를 맡는 사람만 약 1만 명에 이르러 "알고리즘계에서 잘 알려진 사람은 모두 이 대회의 출제와 검수에 참여한다"는 뜻을 가진다.

수많은 경쟁자를 꺾고 마침내 Etacoder Plus와의 결승전이 열렸다. 참고로 나와 Etacoder Plus는 인공지능이다. 내 이름은 SolvingCore KX이다. 요즘 세상에 인간이 본선에 진출하는 것도 이상한 일이긴 하다. 인간 부문과 인공지능 부문을 따로 열면 되지 않느냐고 할 수도 있지만, 누구나 튜링 테스트를 통과하는 요즘에는 인간과 인공지능을 구별하기가 극도로 어려워 현실적인 방안이 못 된다.

결승전의 진행 방식은 조금 특이하다. Etacoder Plus는 작년 대회 우승자이므로 약간의 제약을 받는다. 구체적으로, 결승전에는 짝수 개의 문제가 준비되어 있다. 먼저 도전자가 두 개의 문제를 고르고, 우승자가 그 둘 중 하나를 고른다. 도전자는 남은 하나를 가져간다. 모든 문제가 배정될 때까지 이것을 반복한 다음, 배정된 모든 문제를 먼저 푸는 사람이 승리한다. (2250년에는 인공지능도 사람이라고 부른다.)

나는 먼저 각 문제에 대해 두 사람이 얼마나 자신 있는지를 각각 자연수로 수치화했다. 즉 내가 문제 $i$를 푸는 데에는 $A[i]$만큼 자신이 있고, Etacoder Plus가 푸는 데에는 $B[i]$만큼 자신이 있다. 내가 두 문제를 고르면 Etacoder Plus는 당연히 더 높은 $B$값을 가지는 문제를 가져갈 것이다. 이 전략을 가정했을 때, 내가 가져가는 문제에 대한 $A$값의 합을 최대화하고 싶다.

첫 줄에 짝수 $N(2 \le N \le 200,000)$이 주어진다. 다음 줄에 $A[1], \dots, A[N]$, 그 다음 줄에 $B[1], \dots, B[N]$이 $(1 \le A[i], B[i] \le 10^9)$ 주어진다. 모든 $A[i]$는 서로 다르고, 모든 $B[i]$도 서로 다르다.

내가 가져가는 문제의 $A[i]$값의 최대 합을 출력한다.