Problem:
 Score : 700 points    Problem Statement We have a directed weighted graph with N vertices.
Each vertex has two integers written on it, and the integers written on Vertex i are A_i and B_i .  In this graph, there is an edge from Vertex x to Vertex y for all pairs 1 \leq x,y \leq N , and its weight is {\rm min}(A_x,B_y) .  We will consider a directed cycle in this graph that visits every vertex exactly once.
Find the minimum total weight of the edges in such a cycle.      Constraints  2 \leq N \leq 10^5  1 \leq A_i \leq 10^9  1 \leq B_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  A_1  B_1  A_2  B_2  :  A_N  B_N       Output Print the minimum total weight of the edges in such a cycle.        Sample Input 1 3
1 5
4 2
6 3      Sample Output 1 7  Consider the cycle 1→3→2→1 . The weights of those edges are {\rm min}(A_1,B_3)=1 , {\rm min}(A_3,B_2)=2 and {\rm min}(A_2,B_1)=4 , for a total of 7 .
As there is no cycle with a total weight of less than 7 , the answer is 7 .       Sample Input 2 4
1 5
2 6
3 7
4 8      Sample Output 2 10       Sample Input 3 6
19 92
64 64
78 48
57 33
73 6
95 73      Sample Output 3 227

Solution (Python):
import sys
N = int(sys.stdin.buffer.readline())
AB = list(map(int, sys.stdin.buffer.read().split()))
A = AB[::2]
B = AB[1::2]
ans = min(sum(A), sum(B))
AB.sort()
pivot = AB[N-1]
pivot2 = AB[N]
pivot_idxs = []
pivot2_idxs = []
ans2 = sum(AB[:N])
for i, (a, b) in enumerate(zip(A, B)):
    if a <= pivot and b <= pivot:
        ans = min(ans, ans2)
        print(ans)
        exit()
    if a == pivot or b == pivot:
        pivot_idxs.append(i)
    if a == pivot2 or b == pivot2:
        pivot2_idxs.append(i)

if len(pivot_idxs) == len(pivot2_idxs) == 1 and pivot_idxs[0] == pivot2_idxs[0]:
    ans2 = min(
        ans2 - pivot + AB[N+1],
        ans2 - AB[N-2] + pivot2
    )
else:
    ans2 = ans2 - pivot + pivot2
ans = min(ans, ans2)
print(ans)

Solution (Python):
import bisect
import sys
input = sys.stdin.buffer.readline


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]


sum_a = 0
sum_b = 0
for a, b in info:
    sum_a += a
    sum_b += b
ans = min(sum_a, sum_b)

res = []
for i in range(n):
    a, b = info[i]
    res.append(a)
    res.append(b)
res.sort()
min_half_sum = sum(res[0:n - 2])


for i in range(n):
    a, b = info[i]
    a, b = max(a, b), min(a, b)
    ind1 = bisect.bisect_right(res, a, lo=0, hi=2*n) - 1
    ind2 = bisect.bisect_right(res, b, lo=0, hi=ind1+1) - 1
    
    tmp_ans = min_half_sum
    cnt = 0
    if n - 2 <= ind1:
        tmp_ans += a
    else:
        cnt += 1
    if n - 2 <= ind2:
        tmp_ans += b
    else:
        cnt += 1

    for i in range(n - 2, 2 *n):
        if cnt == 0:
            break
        if i == ind1 or i == ind2:
            continue
        tmp_ans += res[i]
        cnt -= 1
    ans = min(tmp_ans, ans)

print(ans)

Solution (Python):
N=int(input());A=[-1]*N;B=[-1]*N
for i in range(N):A[i],B[i]=map(int,input().split())
ans=min(sum(A),sum(B));t=[(A[i],i) for i in range(N)]+[(B[i],i) for i in range(N)];t.sort();d=[0]*N
for i in range(N):d[t[i][1]]+=1
S=sum(t[i][0] for i in range(N))
if max(d)==2:
    print(S)
else:
    ans2=min(S+max(A[i],B[i])-t[N-1-(t[N-1][1]==i)][0] for i in range(N))
    print(min(ans,ans2))

Solution (Python):
import sys;input=sys.stdin.readline;N=int(input());A=[-1]*N;B=[-1]*N
for i in range(N):
    A[i],B[i]=map(int,input().split())
ans=min(sum(A),sum(B));temp=[(A[i],i) for i in range(N)]+[(B[i],i) for i in range(N)];temp.sort();data=[0]*N
for i in range(N):data[temp[i][1]]+=1
S=sum(temp[i][0] for i in range(N))
if max(data)==2:
    print(S)
else:
    for i in range(N):ans=min(ans,S+max(A[i],B[i])-temp[N-1-(temp[N-1][1]==i)][0]);
    print(ans)

Solution (Python):
import sys,random

input=sys.stdin.readline

N=int(input())
A=[-1]*N;B=[-1]*N
for i in range(N):
    A[i],B[i]=map(int,input().split())

ans=min(sum(A),sum(B))

temp=[(A[i],i) for i in range(N)]+[(B[i],i) for i in range(N)]
temp.sort()

data=[0]*N
for i in range(N):
    val,id=temp[i]
    data[id]+=1
S=sum(temp[i][0] for i in range(N))

for i in range(N):
    if data[i]==2:
        test=S
        ans=min(ans,test)
    elif data[i]==1:
        if temp[N-1][1]!=i:
            test=S+max(A[i],B[i])-temp[N-1][0]
        else:
            test=S+max(A[i],B[i])-temp[N-2][0]
        ans=min(ans,test)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
import bisect
n = int(input())
ab = [list(map(int,input().split())) for i in range(n)]
both = []
for i in range(n):
  both.extend(ab[i])
both.sort()
ans = 10**18
sm = sum(both[:n])
for i in range(n):
  ai = bisect.bisect_left(both,ab[i][0])
  bi = bisect.bisect_left(both,ab[i][1])
  if ai < n and bi < n:
    ans = min(ans,sm)
  elif ai < n-1:
    ans = min(ans,sm-both[n-1]+ab[i][1])
  elif ai == n-1:
    ans = min(ans,sm-both[n-2]+ab[i][1])
  elif bi < n-1:
    ans = min(ans,sm-both[n-1]+ab[i][0])
  elif bi == n-1:
    ans = min(ans,sm-both[n-2]+ab[i][0])
  else:
    ans = min(ans,sm-both[n-1]-both[n-2]+sum(ab[i]))
a,b = list(zip(*ab))
ans = min(ans,sum(a),sum(b))
print(ans)

Solution (Python):
n = int(input())

edge = []
num_list = []

for i in range(n):
    a, b = map(int, input().split())
    edge.append([a, b])
    num_list.append(a)
    num_list.append(b)

num_list.sort()
K = num_list[n-1]

ab = []
ax = []
xb = []

for i in range(n):
    a, b = edge[i]
    if a <= K and b <= K:
        ab.append(edge[i])
    elif a <= K:
        ax.append(edge[i])
    elif b <= K:
        xb.append(edge[i])

if len(ab) > 0:
    ans = sum(num_list[:n])
elif len(ax) == n or len(xb) == n:
    ans = sum(num_list[:n])
else:
    yabai_edge = num_list[n-1:n+1]
    if edge.count(yabai_edge) + edge.count(yabai_edge[::-1]) == 0:
        diff = num_list[n] - num_list[n-1]
    elif len(ax) == 1 and edge.count(yabai_edge) == 1:
        diff = num_list[n] - num_list[n-1]
    elif len(xb) == 1 and edge.count(yabai_edge[::-1]) == 1:
        diff = num_list[n] - num_list[n-1]
    else:
        diff = min(num_list[n+1]-num_list[n-1], num_list[n]-num_list[n-2]) 
    ans = sum(num_list[:n]) + diff

print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())

AB = [tuple(map(int, readline().split())) for _ in range(N)]
A, B = map(list, zip(*AB))

ans = min(sum(A), sum(B))
C = [(A[i], i) for i in range(N)] + [(B[i], i) for i in range(N)]

C.sort()

table = [0]*N
for i in range(N):
    _, idx = C[i]
    table[idx] += 1
if max(table) > 1:
    ans = min(ans, sum(c for (c, _) in C[:N]))

else:
    MAB = list(map(max, AB))
    D = [None]*N
    for i in range(N, 2*N):
        _, idx = C[i]
        D[idx] = i
    
    res = sum(c for (c, _) in C[:N])
    for i in range(N-1):
        _, idx = C[i]
        ans = min(ans, res + MAB[idx] - C[N-1][0])
    ans = min(ans, res + MAB[C[N-1][1]] - C[N-2][0])

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

n=int(input())
A=[]

A1=0
B1=0

for i in range(n):
    a,b=map(int,input().split())
    
    A1+=a
    B1+=b
    
    A.append((a,2*i))
    A.append((b,2*i+1))


ANS=min(A1,B1)

A.sort()
INVIND=[-1]*(2*n)

for ind,(a,i) in enumerate(A):
    INVIND[i]=ind

S=[0]

for a,i in A:
    S.append(S[-1]+a)


for i in range(n):
    if INVIND[i*2]<n and INVIND[i*2+1]<n:
        ANS=min(ANS,S[n])

    elif INVIND[i*2]<n-1 and INVIND[i*2+1]>=n-1:
        ANS=min(ANS,A[INVIND[i*2+1]][0]+S[n-1])

    elif INVIND[i*2]>=n-1 and INVIND[i*2+1]<n-1:
        ANS=min(ANS,A[INVIND[i*2]][0]+S[n-1])

    else:
        ANS=min(ANS,S[n-2]+A[INVIND[i*2]][0]+A[INVIND[i*2+1]][0])

    

print(ANS)

Solution (Python):
N = int(input())
D = []
for i in range(N):
    a, b = map(int, input().split())
    D.append((a, 0, i))
    D.append((b, 1, i))

D.sort()
ans = 0
C = [False] * N
db = False
gr = [0] * 2
for i in range(N):
    ans += D[i][0]
    gr[D[i][1]] += 1
    if C[D[i][2]]:
        db = True
    C[D[i][2]] = True

if not db and gr[0] != 0 and gr[1] != 0:
    if D[N - 1][2] == D[N][2]:
        ans = min(ans - D[N - 2][0] + D[N][0], ans - D[N - 1][0] + D[N + 1][0])
    else:
        ans = ans - D[N - 1][0] + D[N][0]

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

import numpy as np

"""
各辺に対して、Ax,Byの好きな方をとれるとしてよい
全部で半分ずつ → たいてい実現可能

・全部ox
・全部xo
・xx,ooともに存在→ひとつ oo で決め打てば、貪欲に半分とれる
"""

N = int(input())
AB = np.array([[int(x) for x in input().split()] for _ in range(N)],dtype=np.int64)

answer = AB[:,0].sum()
answer = min(answer,AB[:,1].sum())

AB.sort(axis=1)
A,B = AB.T
i = A.argsort()
A = A[i]; B = B[i]

if A.max() > B.min():
    
    C = np.concatenate([A,B])
    C.sort()
    answer = min(answer, C[:N].sum())


x = A[:-1].sum() + B[:-1].min()
y = A[-1]+B[-1] + A[:-2].sum()
answer = min(answer,x,y)

print(answer)

Solution (Python):
N = int(input())
As, Bs = [], []
for i in range(N):
    A, B = map(int, input().split())
    As.append((A, i))
    Bs.append((B, i))

ansA = sum([A for A, i in As])
ansB = sum([B for B, i in Bs])

Cs = sorted(As + Bs)

useds = [False] * N
sumC = 0
for C, i in Cs[:N]:
    useds[i] = True
    sumC += C

if not all(useds):
    ansC = sumC
elif Cs[N-1][1] != Cs[N][1]:
    ansC = sumC - Cs[N-1][0] + Cs[N][0]
else:
    ansC = min(sumC - Cs[N-2][0] + Cs[N][0], sumC - Cs[N-1][0] + Cs[N+1][0])

print(min(ansA, ansB, ansC))

Solution (Python):
import sys
input = sys.stdin.readline
N=int(input())
A=0
B=0
table=[]
for i in range(N):
    a,b=map(int,input().split())
    table.append((a,i))
    table.append((b,i))
    A+=a
    B+=b
ans=min(A,B)
table.sort()
num=0
for i in range(N):
    num+=table[i][0]
L=[0]*N

for i in range(N):
    c,j=table[i]
    if L[j]!=0:
        ans=min(num,ans)
        print(ans)
        
        sys.exit()
    L[j]+=1
c,n=table[N-1]
if n!=table[N][1]:
    num=num-table[N-1][0]+table[N][0]
    ans = min(num, ans)
    print(ans)
    sys.exit()
num1=num-table[N-1][0]+table[N+1][0]
num2=num-table[N-2][0]+table[N][0]
print(min(ans,num1,num2))

Solution (Python):
import sys
N=int(input())
A=0
B=0
table=[]
for i in range(N):
    a,b=map(int,input().split())
    table.append((a,i))
    table.append((b,i))
    A+=a
    B+=b
ans=min(A,B)
table.sort()
num=0
for i in range(N):
    num+=table[i][0]
L=[0]*N

for i in range(N):
    c,j=table[i]
    if L[j]!=0:
        ans=min(num,ans)
        print(ans)
        
        sys.exit()
    L[j]+=1
c,n=table[N-1]
if n!=table[N][1]:
    num=num-table[N-1][0]+table[N][0]
    ans = min(num, ans)
    print(ans)
    sys.exit()
num1=num-table[N-1][0]+table[N+1][0]
num2=num-table[N-2][0]+table[N][0]
print(min(ans,num1,num2))

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
Cost=[]
s1,s2=0,0
for i in range(n):
    a,b=map(int,input().split())
    s1+=a
    s2+=b
    Cost.append([a,i])
    Cost.append([b,i])
Cost.sort()
s3=sum([Cost[i][0] for i in range(n)])
if len(set([Cost[i][1] for i in range(n)]))==n:
    if Cost[n-1][1]==Cost[n][1]:
        s3+=min(Cost[n+1][0]-Cost[n-1][0],Cost[n][0]-Cost[n-2][0])
    else:
        s3+=Cost[n][0]-Cost[n-1][0]
print(min(s1,s2,s3))

Solution (Python):
def mincos(n,ab):
    aball=[]
    aball+=[(ab[i][0],i+1,'a') for i in range(n)]
    aball+=[(ab[i][1],i+1,'b') for i in range(n)]
    aball.sort()
    
    ans1=sum([i[0] for i in aball[:n]])

    hen=aball[n][0]
    hen2=aball[n+1][0]
    d=set()
    t=None
    hantei=True
    for i,c,mab in aball[:n]:
        if t!=None and t!=mab:
            hantei=False
        if  c in d:
            print(ans1)
            exit()
        d.add(c)
        t=mab

    if hantei:
        print(ans1)
        exit()

    ans2=[]
    for i,c,aorb in aball[:n]:
        if aball[n][1]!=c:
            ans2+=[ans1-i+hen]
        else:
            ans2+=[ans1-i+hen2]
    print(min(ans2))
    exit()

n=int(input())
print(mincos(n,[list(map(int,input().split())) for i in range(n)]))

Solution (Python):
def mincos(n,ab):
    aball=[]
    aball+=[(ab[i][0],i+1,'a') for i in range(n)]
    aball+=[(ab[i][1],i+1,'b') for i in range(n)]
    aball.sort()
    
    ans1=sum([i[0] for i in aball[:n]])

    hen=aball[n][0]
    hen2=aball[n+1][0]
    d=set()
    t=None
    hantei=True
    for i,c,mab in aball[:n]:
        if t!=None and t!=mab:
            hantei=False
        if  c in d:
            print(ans1)
            exit()
        d.add(c)
        t=mab

    if hantei:
        print(ans1)
        exit()

    ans2=[]
    for i,c,aorb in aball[:n]:
        if aball[n][1]!=c:
            ans2+=[ans1-i+hen]
        else:
            ans2+=[ans1-i+hen2]
    print(min(ans2))
    exit()

n=int(input())
print(mincos(n,[list(map(int,input().split())) for i in range(n)]))

Solution (Python):
N=int(input())
A=[]
node=[]
for i in range(N):
  x,y=map(int,input().split())
  A.append((x,i,"left"))
  A.append((y,i,"right"))
  node.append((x,y))
  
A.sort()
Used=[[False,False] for i in range(N)]
Used_node=0
for i in range(N):
  if A[i][2]=="left":
    Used[A[i][1]][0]=True
    if not Used[A[i][1]][1]:
      Used_node+=1
  if A[i][2]=="right":
    Used[A[i][1]][1]=True
    if not Used[A[i][1]][0]:
      Used_node+=1
if Used_node!=N:
  ans=0
  for i in range(N):
    ans+=A[i][0]
  print(ans)
else:
  if Used[0][0]:
    f=0
  else:
    f=1
  NO=0
  for i in range(N):
    if not Used[i][f]:
      NO=1
      break
  ans=0
  for i in range(N):
    ans+=A[i][0]
  ans2=float("inf")
  if NO==1:
    for w in range(N):
      if A[N][1]==w:
        ans2=min(ans2,ans-min(node[w])+A[N+1][0])
      else:
        ans2=min(ans2,ans-min(node[w])+A[N][0])
    print(ans2)
    exit()
  print(ans)

Solution (Python):
N = int(input())
A = []
B = []
Sa = 0
Sb = 0
for i in range(N):
    a,b = map(int,input().split())
    A.append([a,i])
    B.append([b,i])
    Sa += a
    Sb += b
C = sorted(A+B)
ind = []
ans = 0
for i in range(N):
    ind.append(C[i][1])
    ans += C[i][0]
ind = set(ind)
if len(ind) == N:
    if C[N-1][1] != C[N][1]:
        ans += C[N][0]-C[N-1][0]
    else:
        ans += min(C[N][0]-C[N-2][0],C[N+1][0]-C[N-1][0])
ans = min(Sa,Sb,ans)
print(ans)

Solution (Python):
import sys
import socket

if socket.gethostname() in ['N551J', 'F551C']:
    test_case = 'c1.in'
    sys.stdin = open(test_case)


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    n = read_int()
    rows = [read_int_list() for i in range(n)]
    a, b = map(list, zip(*rows))
    res = sum(a)
    res = min(res, sum(b))
    all_values = [(a[i], i, 0) for i in range(n)]
    all_values.extend([(b[i], i, 1) for i in range(n)])
    all_values.sort()
    index_of_value = {v: i for i, v in enumerate(all_values)}
    first_values = [
        set(all_values[:n - 2]),
        set(all_values[:n - 1]),
        set(all_values[:n]),
    ]

    s = [sum([t[0] for t in v]) for v in first_values]
    for i in range(n):
        rest = []
        k = 0
        last = n - 2
        indices = sorted([(index_of_value[(a[i], i, 0)], a[i]),
                          (index_of_value[(b[i], i, 1)], b[i])])

        for index, value in indices:
            if index < last:
                last += 1
                k += 1
            else:
                rest.append(value)
        t = s[k] + sum(rest)
        res = min(res, t)
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
'''
辺のコストをmin(Ax, By)とする代わりに、
辺のコストをAxもしくはByの好きな方にしてよいとしたときの最小値を求める

各頂点vについて、
１．Av, Bvともに選ばれる
２．Avのみ選ばれる
３．Bvのみ選ばれる
４．Av, Bvとも選ばれない

すべてタイプ2のときはsum(A), すべてタイプ3のときはsum(B)
それ以外は、タイプ1 = タイプ4 
2...2 4141..4 3...3 1
と構成すればよい
A, Bを合併したリストから小さい順にN個取る
この時に、最初のN個に同じ頂点由来のAv, Bvが両方含まれていたら上のように構成してしまえばよい
明らかにこれが最小値
含まれていないときは, 最初のn項についてそれぞれ取り除いたときにどうなるかを考える
Aw/Bwを取り除いたとすると, N+1番目の項がBw/AwでなければN+1番目の項を追加
Bw/Awの時はN+2番目の項を追加
（最初のN項が頂点について被りがないという条件から、これにより必ずあるvについてAv, Bv両方が含まれることになる
'''

n = int(input())
x = []
for i in range(n):
    ai, bi = map(int, input().split())
    x += [[i, ai, 0], [i, bi, 1]]
s1 = sum([x[2 * i][1] for i in range(n)])
s2 = sum([x[2 * i + 1][1] for i in range(n)])


x.sort(key = lambda x: x[1])
s3 = sum([x[i][1] for i in range(n)])
if len(set([x[i][0] for i in range(n)])) != n:
    print(min(s1, s2, s3))
else:
    if x[n - 1][0] == x[n][0]:
        s4 = min(s3 - x[n - 1][1] + x[n + 1][1], s3 - x[n - 2][1] + x[n][1])
    else:
        s4 = s3 - x[n - 1][1] + x[n][1]
    print(min(s1, s2, s4))

Solution (Python):
N = int(input())
import sys

all_list = []
counter = 1
for line in sys.stdin:
    a, b = [int(x) for x in line.strip().split(" ")]
    all_list += [("a", counter, a), ("b", counter, b)]
    counter += 1

all_list = sorted(all_list, key = lambda x : x[2])

sp_c = all_list[N][1]
sp_i_p = all_list[N][2]
sp_i_pp = all_list[N+1][2]

flag = True
ss = sum([i[2] for i in all_list[:N]])
d = set()
temp = None
for ab, c, i in all_list[:N]:
    if temp != None and temp != ab:
        flag = False
    if c in d:
        flag = True
        break
    d.add(c)
    temp = ab
if flag:
    print(ss)
else:
    candidates = []
    for ab, c, i in all_list[:N]:
        if sp_c != c:
            candidates.append(ss - i + sp_i_p)
        else:
            candidates.append(ss - i + sp_i_pp)
    print(min(candidates))

Solution (Python):
n = int(input())
b = []
ASUM = 0
BSUM = 0
for i in range(n):
  x,y = map(int,input().split())
  b.append([x,i])
  b.append([y,i])
  ASUM += x
  BSUM += y
a = sorted(b)
tuka = [0] * n
flag = 0
for i in range(n):
  if tuka[a[i][1]] == 1:
    flag = 1
    break
  else:
    tuka[a[i][1]] = 1
ans = 0
for i in range(n):
  ans += a[i][0]
if flag == 0:
  tmp = float("inf")
  las = a[n-1]
  bu = a[n-2]
  for i in range(n):
    if las[1] == i:
      tmp = min(tmp,max(b[i*2][0],b[i*2+1][0])-bu[0])
    else:
      tmp = min(tmp,max(b[i*2][0],b[i*2+1][0])-las[0])
  ans += tmp
ans = min(ans,ASUM,BSUM)
print(ans)

Solution (Python):
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N)]

suma = sumb = 0
elems = []
for i,(a,b) in enumerate(src):
    suma += a
    sumb += b
    elems.append((a,i))
    elems.append((b,i))
ans = min(suma, sumb)
elems.sort()

sumw = 0
used = [0]*N
dup = False
for w,i in elems[:N]:
    sumw += w
    used[i] += 1
    if used[i] > 1: dup = True

if dup:
    ans = min(ans, sumw)
    print(ans)
    exit()

for i,(a,b) in enumerate(src):
    if a > b:
        a,b = b,a
    neww = elems[N][0] if i != elems[N][1] else elems[N+1][0]
    tmp = sumw - a + neww
    ans = min(ans, tmp)
print(ans)

Solution (Python):

from heapq import heappush, heappop

N = int(input())
values = [0]*(2*N)

for i in range(N):
    A, B = map(int, input().split())
    values[i] = A
    values[i+N] = B

def argsort(R_arr):
    N = len(R_arr)
    R_args = [0]*N
    R_vars = [0]*N
    h = []
    for i in range(N):
        heappush(h, (R_arr[i], i))
    for i in range(N):
        a, b = heappop(h)
        R_args[i] = b
        R_vars[i] = a
    return R_vars, R_args

values_sorted, args = argsort(values)


picked = [0]*N

for i in range(N):
    picked[args[i] % N] = 1
    
if sum(picked) == N:
    if args[N-1] % N == args[N] % N:
        res1 = sum(values_sorted[:(N-1)]) + values_sorted[N+1]
        res2 = sum(values_sorted[:(N+1)]) - values_sorted[N-2]
        res = min(res1, res2)
    else:
        res = sum(values_sorted[:(N-1)]) + values_sorted[N]
    res3 = sum(values[:N])
    res4 = sum(values[N:])
    res = min(res, res3, res4)
else:
    res = sum(values_sorted[:N])

print(res)

Solution (Python):
N = int(input())
A = []
B = []
for i in range(N):
    a, b = map(int, input().split())
    A += [a]
    B += [b]
s1 = sum(A)
s2 = sum(B)
C = A + B
C.sort()
s3 = sum(C[:N])
s4 = sum(C[N:])
check = 1
m1 = C[N-1]
m2 = C[N-2]
for i in range(N):
    a = min(A[i], B[i])
    b = max(A[i], B[i])
    if b < m1:
        check = 0
        break
    elif b == m1 and a != b:
        check = 0
        break
    elif a < m1:
        s4 = min(s4, s3 - m1 + b)
    elif a == m1:
        s4 = min(s4, s3 - m2 + b)
if check == 0:
    print(min(s1, s2, s3))
else:
    print(min(s1, s2, s4))

Solution (Python):
n=int(input())
a=[]
b=[]
for i in range(n):
    p,q=map(int,input().split())
    a.append((p,i,0))
    a.append((q,i,1))
a.sort(key=lambda x:x[0])
result=0
l=[0]*n
flag=0
for i in range(n):
    if l[a[i][1]]==1:
        flag=1
        break
    else:
        l[a[i][1]]=1
t=a[0][2]
s=0
for i in range(n):
    s+=a[i][2]-a[0][2]
if s==0:
    flag=1
if flag==1:

    for i in range(n):
        result+=a[i][0]
    print(result)
else:
    if a[n-1][1]==a[n][1]:
        for i in range(n):
            result+=a[i][0]
        result+=min(a[n+1][0]-a[n-1][0],a[n][0]-a[n-2][0])
        print(result)
    else:
        for i in range(n):
            result+=a[i][0]
        result+=a[n][0]-a[n-1][0]
        print(result)

Solution (Python):
from operator import itemgetter
from itertools import chain

n = int(input())
aaa = [tuple(map(int, input().split())) for _ in range(n)]
flatten = sorted(chain.from_iterable([(a, i), (b, i)] for i, (a, b) in enumerate(aaa)))
picked = set()
ans = 0

for ab, i in flatten[:n]:
    picked.add(i)
    ans += ab

if len(picked) == n:
    exclude = flatten[n - 1]
    include = flatten[n]
    if exclude[1] == include[1]:
        tmp1 = include[0] - flatten[n - 2][0]
        tmp2 = flatten[n + 1][0] - exclude[0]
        ans += min(tmp1, tmp2)
    else:
        ans -= exclude[0]
        ans += include[0]

ans = min(ans, sum(map(itemgetter(0), aaa)), sum(map(itemgetter(1), aaa)))

print(ans)

Solution (Python):
from operator import itemgetter
from itertools import chain

n = int(input())
aaa = [tuple(map(int, input().split())) for _ in range(n)]
flatten = list(chain.from_iterable([(a, i), (b, i)] for i, (a, b) in enumerate(aaa)))
flatten.sort()
flag = True
picked = set()
ans = 0

for ab, i in flatten[:n]:
    if flag and i in picked:
        flag = False
    picked.add(i)
    ans += ab

if flag:
    exclude = flatten[n - 1]
    include = flatten[n]
    if exclude[1] == include[1]:
        tmp1 = include[0] - flatten[n - 2][0]
        tmp2 = flatten[n + 1][0] - exclude[0]
        ans += min(tmp1, tmp2)
    else:
        ans -= exclude[0]
        ans += include[0]

ans = min(ans, sum(map(itemgetter(0), aaa)), sum(map(itemgetter(1), aaa)))

print(ans)

Solution (Python):





"""
AGC028 C
"""

from operator import itemgetter

n = int(input())
abli = []
for i in range(n):
    a, b = map(int, input().split())
    abli.append((a, i, 0))
    abli.append((b, i, 1))

abli.sort(key=itemgetter(0))
tmpans0 = sum(map(itemgetter(0), abli[:n]))
aiset = set([i for x, i, aorb in abli[:n] if not aorb])
biset = set([i for x, i, aorb in abli[:n] if aorb])
flag = bool(set.intersection(aiset, biset))


y, j, arob2 = abli[n]
z, k, arob3 = abli[n+1]

if flag:
    tmpans = tmpans0
else:
    min1 = y-max([x for x, i, aorb in abli[:n] if j != i])
    min2 = z-max([x for x, i, aorb in abli[:n] if j == i])
    tmpans = tmpans0 + min(min1, min2)

leftsum = sum([aa for aa, i, aorb in abli if not aorb])
rightsum = sum([bb for bb, i, aorb in abli if aorb])

print(min(leftsum, rightsum, tmpans))

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()
ls = []
A_ = []
B_ = []
for i in range(N):
    A, B = map(int, raw_input().split())
    A_.append(A)
    B_.append(B)
    ls.append((A, 'A', i))
    ls.append((B, 'B', i))

ls.sort()

used = [[False] * N, [False] * N]

S = 0
for i in range(N):
    p = ls[i]
    S += p[0]
    if p[1] == 'A':
        used[0][p[2]] = True
    else:
        used[1][p[2]] = True

if True in used[0] and True in used[1]:
    pass
else:
    print S
    exit()

for i in range(N):
    if used[0][i] and used[1][i]:
        print S
        exit()

ans = INF
for i in range(N):
    T = S
    pos = N
    if ls[pos][2] == i:
        pos += 1
    if used[0][i]:
        T -= A_[i]
        T += ls[pos][0]
    else:
        T -= B_[i]
        T += ls[pos][0]
    ans = min(ans, T)

print ans

Solution (Python):
n = int(input())
c = []
not_c = []
chosen = set()
ans = 0
for i in range(n):
	a, b = map(int, input().split())
	not_c.append([max(a, b), i])
	c.append([min(a, b), i])
	ans += min(a, b)
	if a < b:
		chosen.add("a")
	elif a > b:
		chosen.add("b")

if len(chosen) < 2:
	print(ans)
else:
	c = sorted(c, reverse=True)
	not_c = sorted(not_c)
	
	
	

	if c[0][1] != not_c[0][1]:
		ans = ans - c[0][0] + not_c[0][0]
		c_cur = 1
		not_cur = 1
	else:
		ans = min(ans - c[1][0] + not_c[0][0], ans - c[0][0] + not_c[1][0])
		if ans - c[1][0] + not_c[0][0] <= ans - c[0][0] + not_c[1][0]:
			c_cur = 2
			not_cur = 1
		else:
			c_cur = 1
			not_cur = 2
	if c_cur < n and not_cur < n:
		while c[c_cur][0] > not_c[not_cur][0]:
			if c[c_cur][1] != not_c[not_cur][1]:
				ans = ans - c[c_cur][0] + not_c[not_cur][0]
				c_cur += 1
				not_cur += 1
			else:
				ans = min(ans - c[c_cur+1][0] + not_c[not_cur][0], ans - c[c_cur][0] + not_c[not_cur+1][0])
				if ans - c[c_cur+1][0] + not_c[not_cur][0] <= ans - c[c_cur][0] + not_c[not_cur+1][0]:
					c_cur += 2
					not_cur += 1
				else:
					c_cur += 1
					not_cur += 2
			if c_cur >= n or not_cur >= n:
				break
	print(ans)

Solution (Python):
n = int(input())
c = []
not_c = []
chosen = set()
ans = 0
for i in range(n):
	a, b = map(int, input().split())
	not_c.append([max(a, b), i])
	c.append([min(a, b), i])
	ans += min(a, b)
	if a < b:
		chosen.add("a")
	elif a > b:
		chosen.add("b")

if len(chosen) < 2:
	print(ans)
else:
	c = sorted(c, reverse=True)
	not_c = sorted(not_c)
	
	
	

	if c[0][1] != not_c[0][1]:
		ans = ans - c[0][0] + not_c[0][0]
		c_cur = 1
		not_cur = 1
	else:
		ans = min(ans - c[1][0] + not_c[0][0], ans - c[0][0] + not_c[1][0])
		if ans - c[1][0] + not_c[0][0] <= ans - c[0][0] + not_c[1][0]:
			c_cur = 2
			not_cur = 1
		else:
			c_cur = 1
			not_cur = 2
	if c_cur < n and not_cur < n:
		while c[c_cur][0] > not_c[not_cur][0]:
			if c[c_cur][1] != not_c[not_cur][1]:
				ans = ans - c[c_cur][0] + not_c[not_cur][0]
				c_cur += 1
				not_cur += 1
			elif c_cur == n - 1 or not_cur == n - 1:
				break
			else:
				ans = min(ans - c[c_cur+1][0] + not_c[not_cur][0], ans - c[c_cur][0] + not_c[not_cur+1][0])
				if ans - c[c_cur+1][0] + not_c[not_cur][0] <= ans - c[c_cur][0] + not_c[not_cur+1][0]:
					c_cur += 2
					not_cur += 1
				else:
					c_cur += 1
					not_cur += 2
			if c_cur >= n or not_cur >= n:
				break
	print(ans)

Solution (Python):

N = int(input())
pairs = []
for i in range(N):
    tmp = input()
    pairs.append([int(a) for a in tmp.split()])

pos_and_vals = []
for i, (from_, to_) in enumerate(pairs):
    pos_and_vals.append(((i, 0), from_))
    pos_and_vals.append(((i, 1), to_))

pos_and_vals_sorted = sorted(pos_and_vals, key=(lambda x: x[1]))
pos_and_vals_sorted_toN = pos_and_vals_sorted[:N]

directions = [[False, False] for _ in range(N)]
for (i, direction), val in pos_and_vals_sorted_toN:
    directions[i][direction] = True

smallest_sum = sum([val for (i, direction), val in pos_and_vals_sorted_toN])
first_direction = pos_and_vals_sorted[0][0][1]
if all([direction == first_direction for (i, direction), val in pos_and_vals_sorted_toN]):
    
    
    answer = smallest_sum
elif any([(not direction[0]) and (not direction[1]) for direction in directions]):
    
    answer = smallest_sum
else:
    highest_inner = pos_and_vals_sorted[N-1]
    lowest_outer = pos_and_vals_sorted[N]
    if highest_inner[0][0] != lowest_outer[0][0]:
        
        answer = smallest_sum - highest_inner[1] + lowest_outer[1]
    elif all([direction == lowest_outer[0][1]
              for (i, direction), val in pos_and_vals_sorted_toN[:N-1]]):
        
        answer = smallest_sum - highest_inner[1] + lowest_outer[1]
    else:
        assert N >= 2
        
        second_highest_inner = pos_and_vals_sorted[N-2]
        second_lowest_outer = pos_and_vals_sorted[N + 1]
        candidate_one = smallest_sum - second_highest_inner[1] + lowest_outer[1]
        candidate_two = smallest_sum - highest_inner[1] + second_lowest_outer[1]
        answer = min(candidate_one, candidate_two)

print(answer)

Solution (Python):
import sys
n=input()
pair=[]
sort=[]
for i in range(n):
	a, b=map(int, raw_input().split())
	pair.append([[a, 0], [b, 0]])
	sort.append((a, i, 0))
	sort.append((b, i, 1))
sum=0
sort.sort()
for i in range(n):
	assert pair[sort[i][1]][sort[i][2]][0]==sort[i][0]
	pair[sort[i][1]][sort[i][2]][1]=1
	sum+=sort[i][0]
cnt=[[0, 0], [0, 0]]
for i in range(n):
	cnt[pair[i][0][1]][pair[i][1][1]]+=1
assert cnt[0][0]==cnt[1][1]
if cnt[0][0]>0 or cnt[0][1]==n or cnt[1][0]==n:
	print sum
else:
	min_value=1000000000000000000
	max_value=-1
	for i in range(n):
		if pair[i][0][1]:
			assert pair[i][1][1]==0
			min_value=min(min_value, pair[i][1][0])
			max_value=max(max_value, pair[i][0][0])
		else:
			assert pair[i][1][1]==1
			min_value=min(min_value, pair[i][0][0])
			max_value=max(max_value, pair[i][1][0])
	min_id=-1
	max_id=-1
	for i in range(n):
		if pair[i][0][1]:
			assert pair[i][1][1]==0
			if min_value==pair[i][1][0]:
				min_id=i
			if max_value==pair[i][0][0]:
				max_id=i
		else:
			assert pair[i][1][1]==1
			if min_value==pair[i][0][0]:
				min_id=i
			if max_value==pair[i][1][0]:
				max_id=i
	assert min_value>=max_value
	if min_id!=max_id:
		print sum-max_value+min_value
	else:
		new_min_value=1000000000000000000
		new_max_value=-1
		for i in range(n):
			if i==min_id:
				continue
			if pair[i][0][1]:
				new_min_value=min(new_min_value, pair[i][1][0])
				new_max_value=max(new_max_value, pair[i][0][0])
			else:
				assert pair[i][1][1]==1
				new_min_value=min(new_min_value, pair[i][0][0])
				new_max_value=max(new_max_value, pair[i][1][0])
		print min(sum-max_value+new_min_value, sum-new_max_value+min_value)
		print>>sys.stderr, "\n\n\n"

Solution (Python):
from sys import stdin
from heapq import heapify, heappop
from itertools import repeat
def main():
    n = int(stdin.readline())
    dat = map(int, stdin.read().split(), repeat(10, 2 * n))
    q = [(x, i) for i, x in enumerate(dat)]
    q.sort()
    d = [0] * n
    ans = min(sum(dat[::2]), sum(dat[1::2]))
    s = 0
    for i in xrange(n):
        s += q[i][0]
        d[q[i][1]/2] |= 1 << (q[i][1] % 2)
    for i in xrange(n):
        p = s
        c = n - 1
        for j in xrange(2):
            if not (d[i] >> j & 1):
                p += dat[i*2+j]
                while q[c][1] / 2 == i:
                    c -= 1
                p -= q[c][0]
                c -= 1
        if ans > p:
            ans = p
    print ans
main()

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
A = [0] * N; B = [0] * N
for i in range(N):
  A[i], B[i] = reads()

ans = 10 ** 18
ans = min(ans, sum(A))
ans = min(ans, sum(B))

s = sorted([(A[i], i) for i in range(N)] + [(B[i], i) for i in range(N)])

used = [False] * N
for i in range(N):
  used[s[i][1]] = True
cand = sum(a for a, i in s[:N])
if not all(used):
  ans = min(ans, cand)
else:
  if s[N-1][1] != s[N][1]:
    ans = min(ans, cand - s[N-1][0] + s[N][0])
  else:
    ans = min(ans, cand - s[N-2][0] + s[N][0])
    ans = min(ans, cand - s[N-1][0] + s[N+1][0])
print(ans)