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



Sample input:
3
1 5
4 2
6 3


Sample output:
7

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
ab = [None]*n
ma = float("inf")
mb = float("inf")
for i in range(n):
    a,b = tuple(map(int, input().split()))
    ab[i] = (a,b)
    ma = min(ma, a)
    mb = min(mb, b)
# if ma>mb:
#     ab = [(item[1], item[0]) for item in ab]
class UnionFindTree:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.size = [1] * n

    def root(self, i):
        inter = set()
        while self.parent[i]!=i:
            inter.add(i)
            i = self.parent[i]
        r = i
        for i in inter:
            self.parent[i] = r
        return r

    def connect(self, i, j):
        if i==j:
            return
        ri = self.root(i)
        rj = self.root(j)
        if ri==rj:
            return
        if self.size[ri]<self.size[rj]:
            self.parent[ri] = rj
            self.size[rj] += self.size[ri]
        else:
            self.parent[rj] = ri
            self.size[ri] += self.size[rj]
    
uf = UnionFindTree(n)

    
done = [False] * n
ab.sort()
h = []
from heapq import heappop as hpp, heappush as hp
for i,item in enumerate(ab):
    hp(h, (-item[1], i))
ans = 0
# print(h)
for i in range(n-1):
    tmp = tmp2 = None
    if h[0][1]==i or uf.root(h[0][1])==uf.root(i):
        tmp = hpp(h)
        if h[0][1]==i or uf.root(h[0][1])==uf.root(i):
            tmp2 = hpp(h)
    item = hpp(h)
    if tmp is not None:
        hp(h, tmp)
    if tmp2 is not None:
        hp(h, tmp2)
    uf.connect(i, item[1])
#     print(ab[i][0], -item[0])
    ans += min(ab[i][0], -item[0])
ans += min(ab[n-1][0], -h[0][0])
ans = min(ans, sum(item[0] for item in ab), sum(item[1] for item in ab))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
ab = [None]*n
ma = float("inf")
mb = float("inf")
for i in range(n):
    a,b = tuple(map(int, input().split()))
    ab[i] = (a,b)
    ma = min(ma, a)
    mb = min(mb, b)
# if ma>mb:
#     ab = [(item[1], item[0]) for item in ab]
class UnionFindTree:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.size = [1] * n

    def root(self, i):
        inter = set()
        while self.parent[i]!=i:
            inter.add(i)
            i = self.parent[i]
        r = i
        for i in inter:
            self.parent[i] = r
        return r

    def connect(self, i, j):
        if i==j:
            return
        ri = self.root(i)
        rj = self.root(j)
        if ri==rj:
            return
        if self.size[ri]<self.size[rj]:
            self.parent[ri] = rj
            self.size[rj] += self.size[ri]
        else:
            self.parent[rj] = ri
            self.size[ri] += self.size[rj]
    
uf = UnionFindTree(n)

    
done = [False] * n
ab.sort()
h = []
from heapq import heappop as hpp, heappush as hp
for i,item in enumerate(ab):
    hp(h, (-item[1], i))
ans = 0
# print(h)
for i in range(n-1):
    tmp = tmp2 = None
    if h[0][1]==i or uf.root(h[0][1])==uf.root(i):
        tmp = hpp(h)
        if h[0][1]==i or uf.root(h[0][1])==uf.root(i):
            tmp2 = hpp(h)
    item = hpp(h)
    if tmp is not None:
        hp(h, tmp)
    if tmp2 is not None:
        hp(h, tmp2)
    uf.connect(i, item[1])
#     print(ab[i][0], -item[0])
    ans += min(ab[i][0], -item[0])
ans += min(ab[n-1][0], -h[0][0])
print(ans)

Submission status: Wrong Answer

Solution code:
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:
    ans=min(S+max(A[i],B[i])-t[N-1-(t[N-1][1]==i)][0] for i in range(N))
    print(ans)

Submission status: Wrong Answer

Solution code:
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):
    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
    elif data[i]==1:
        test=S+max(A[i],B[i])-temp[N-1][0]
    else:
        test=S+A[i]+B[i]-temp[N-1][0]-temp[N-2][0]
    ans=min(test,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
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:
    ans = min(ans,sm-both[n-1]+ab[i][1])
  elif bi < n:
    ans = min(ans,sm-both[n-1]+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)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from heapq import heappush, heappop, heapify
    input = sys.stdin.buffer.readline

    N = int(input())
    L = []
    R = []
    LR = []
    for i in range(N):
        a, b = map(int, input().split())
        L.append((-a, i))
        R.append((b, i))
        LR.append((a, b))
    heapify(L)
    heapify(R)

    used = set()
    ans = 0
    for new_id in range(N, N*2-1):
        while True:
            l_, id_L = heappop(L)
            l = -l_
            if id_L in used:
                continue
            else:
                break
        while True:
            r, id_R = heappop(R)
            if id_R in used:
                continue
            else:
                break
        if id_L == id_R:
            while True:
                l_2, id_L2 = heappop(L)
                l2 = -l_2
                if id_L2 in used:
                    continue
                else:
                    heappush(L, (l_, id_L))
                    l = l2
                    id_L = id_L2
                    break
        used.add(id_L)
        used.add(id_R)
        ans += min(LR[id_L][0], LR[id_R][1])
        LR.append((LR[id_R][0], LR[id_L][1]))
        heappush(L, (-LR[id_R][0], new_id))
        heappush(R, (LR[id_L][1], new_id))

    ans += min(LR[-1][0], LR[-1][1])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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:
    ax_xmin = min(map(lambda x:x[1], ax))
    ax_amax = max(map(lambda x:x[0], ax))
    xb_xmin = min(map(lambda x:x[0], xb))
    xb_bmax = max(map(lambda x:x[1], xb))

    diff = min(xb_xmin - ax_amax, ax_xmin - xb_bmax)
    if len(ax) == 1 or len(xb) == 1:
        diff = min(diff, ax_xmin - ax_amax, xb_xmin - xb_bmax)
    ans = sum(num_list[:n]) + diff

print(ans)

Submission status: Wrong Answer

Solution code:
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 = 0
ax = 0
xb = 0

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

if ab > 0:
    ans = sum(num_list[:n])
elif ax == n or xb == n:
    ans = sum(num_list[:n])
else:
    ans = sum(num_list[:n-1]) + num_list[n]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

n=int(sys.stdin.readline())
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 and INVIND[i*2+1]>=n:
        ANS=min(ANS,A[INVIND[i*2+1]][0]+S[n-1])

    elif INVIND[i*2]>=n and INVIND[i*2+1]<n:
        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)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

import numpy as np

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

・全部ox
・全部xo
・4種とも1度以上ある→ひとつ 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

if AB[:,0].max() > AB[:,1].min():
    # 全体から貪欲にN個
    C = np.concatenate([A,B])
    C.sort()
    answer = min(answer, C[:N].sum())

# 全体から両取りを1つ
x = A[:-1].sum() + B[:-1].min()
y = A[-1]+B[-1] + A[:-2].sum()
answer = min(answer,x,y)

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

import numpy as np

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

・全部ox
・全部xo
・4種とも1度以上ある→ひとつ xx で決め打てば、貪欲に半分とれる
→ xxに決め打つのは、捨てる恩恵の大きいものとしてよい → 小さい側が大きい
"""

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

A = AB[:,0]
B = AB[:,1]

x = AB[:,0].sum()
y = AB[:,1].sum()

i = np.argmax(np.minimum(A,B))

C = np.delete(AB,i,axis=0).ravel()
C.sort()
z = C[:N].sum()

answer = min(x,y,z)
print(answer)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append(a)
    l.append(b)
l.sort()
print(sum(l[:n]))

Submission status: Wrong Answer

Solution code:
n = int(input())
m = []
for i in range(n):
  m += input().split()
a = list(map(int, m))
ans = 0
a.sort()
print(sum(a[:n]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a, b = [], []
for _ in range(n): 
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)
a.sort()
b.sort(reverse = True)
ret = 0
for i in range(n):
    ret += min(a[i], b[i])
print(ret)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N=int(input())
A=[0 for i in range(N)]
B=[0 for i in range(N)]
t=10**10
s=0
for i in range(N):
    a,b=map(int,input().split())
    A[i]=a
    B[i]=b
    if t>min(a,b):
        t=min(a,b)
        s=i
T=deepcopy(A)
S=deepcopy(B)
if t==A[s]:
    ans=0
    ans+=t
    i=s
    M = T[:i] + T[i + 1:]
    L=S[:i]+S[i+1:]
    L.remove(max(L))
    L+=M+S[i:i+1]
    L.sort()
    ans+=sum(L[:N-1])
    #print(L, M, t)
    print(ans)
else:
    ans=0
    ans+=t
    i=s
    M = T[:i] + T[i + 1:]
    L=S[:i]+S[i+1:]
    M.remove(max(M))
    #print(L,M,t,)
    M+=L+T[i:i+1]
    M.sort()
    ans+=sum(M[:N-1])
    print(ans)

Submission status: Wrong Answer

Solution code:
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 A[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)

Submission status: Wrong Answer

Solution code:
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[i][1]:
      Used_node+=1
  if A[i][2]=="right":
    Used[A[i][1]][1]=True
    if not Used[i][0]:
      Used_node+=1
if Used_node!=N:
  ans=0
  for i in range(N):
    ans+=A[i][0]
  print(ans)
else:
  if A[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)

Submission status: Wrong Answer

Solution code:
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[i][0]=True
    if not Used[i][1]:
      Used_node+=1
  if A[i][2]=="right":
    Used[i][1]=True
    if not Used[i][0]:
      Used_node+=1
if Used_node!=N:
  ans=0
  for i in range(N):
    ans+=A[i][0]
  print(ans)
else:
  if A[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(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
for i in range(N):
  x,y=map(int,input().split())
  A.append((x,i,"left"))
  A.append((y,i,"right"))
  
A.sort()
Used=[[False,False] for i in range(N)]
Used_node=0
for i in range(N):
  if A[i][2]=="left":
    Used[i][0]=True
    if not Used[i][1]:
      Used_node+=1
  if A[i][2]=="right":
    Used[i][1]=True
    if not Used[i][0]:
      Used_node+=1
if Used_node!=N:
  ans=0
  for i in range(N):
    ans+=A[i][0]
  print(ans)
else:
  if A[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]
  if NO==1:
    ans+=A[N][0]-A[N-1][0]
  print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
C = [list(map(int,input().split())) for i in range(N)]
C.sort()
ans0 = 0
ans1 = 0
ans2 = 0
A = []
B = []
for i in range(N):
    ans0 += C[i][0]
    ans1 += C[i][1]
    Min = min(C[i][0],C[i][1])
    Max = max(C[i][0],C[i][1])
    ans2 += Min
    A.append(Min)
    B.append(Max)
ans3 = sum(sorted(A+B)[:N])
if ans3 == ans2:
    ans2 -= max(A)
    ans2 += min(B)
    ans3 = ans2
ans = min(ans0,ans1,ans3)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
C = [list(map(int,input().split())) for i in range(N)]
C.sort()
ans0 = 0
ans1 = 0
ans2 = 0
A = []
B = []
for i in range(N):
    ans0 += C[i][0]
    ans1 += C[i][1]
    Min = min(C[i][0],C[i][1])
    Max = max(C[i][0],C[i][1])
    ans2 += Min
    A.append(Min)
    B.append(Max)
ans2 -= max(A)
ans2 += min(B)
ans = min(ans0,ans1,ans2)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
C = [list(map(int,input().split())) for i in range(N)]
C.sort()
ans0 = 0
ans1 = 0
A = []
B = []
for i in range(N):
    ans0 += C[i][0]
    Min = min(C[i][0],C[i][1])
    Max = max(C[i][0],C[i][1])
    ans1 += Min
    A.append(Min)
    B.append(Max)
ans1 -= max(A)
ans1 += min(B)
ans = min(ans0,ans1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import socket

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


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
        if index_of_value[(a[i], i, 0)] < n:
            k += 1
        else:
            rest.append(a[i])
        if index_of_value[(b[i], i, 1)] < n:
            k += 1
        else:
            rest.append(b[i])
        t = s[k] + sum(rest)
        res = min(res, t)
    return res


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys


n=int(sys.stdin.readline())
A=[list(map(int,sys.stdin.readline().split())) for i in range(n)]
A.sort()
A.sort(key=lambda x:x[1])

LIST=[]
CHECKED=[0]*(n+1)

for i in range(n):
    LIST.append((A[i][0],i,0))
    LIST.append((A[i][1],i,1))
LIST.sort()

from collections import deque

LIST=deque(LIST)

ANS=0
for ro in range(n//2):
    ANS+=LIST[0][0]
    for j in range(len(LIST)-1,-1,-1):
        if LIST[j][1]!=LIST[0][1] and LIST[j][2]!=LIST[0][2] and (CHECKED[LIST[0][1]]==0 or CHECKED[LIST[j][1]]==0):
            #print(LIST,LIST[0],LIST[j])
            CHECKED[LIST[j][1]]=1
            CHECKED[LIST[0][1]]=1
                                                                    
                                                                      
            del LIST[j]
            LIST.popleft()
            break

for ro in range(n//2,n):
    ANS+=LIST[0][0]
    for j in range(len(LIST)-1,-1,-1):
        if LIST[j][1]!=LIST[0][1] and LIST[j][2]!=LIST[0][2]:
            #print(LIST,LIST[0],LIST[j])
            CHECKED[LIST[j][1]]=1
            CHECKED[LIST[0][1]]=1
                                                                    
                                                                      
            del LIST[j]
            LIST.popleft()
            break


print(ANS)

Submission status: Wrong Answer

Solution code:
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
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)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
b=[]
for i in range(n):
    p,q=map(int,input().split())
    a.append(p)
    a.append(q)
a.sort()
result=0
for i in range(n):
    result+=a[i]
print(result)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from itertools import chain

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

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

if flag:
    exclude = flat[n - 1]
    include = flat[n]
    if exclude[1] == include[1]:
        include = flat[n + 1]
    ans -= exclude[0]
    ans += include[0]

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

print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from itertools import chain

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

for ab, i in flat[:len(flat) // 2]:
    if flag and i in picked:
        flag = False
    picked.add(i)
    ans += ab

if flag:
    ans -= flat[len(flat) // 2 - 1][0]
    ans += flat[len(flat) // 2][0]

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

print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from itertools import chain

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

for ab, i in flat[:len(flat) // 2]:
    if flag and i in picked:
        flag = False
    ans += ab

if flag:
    ans -= flat[len(flat) // 2 - 1][0]
    ans += flat[len(flat) // 2][0]

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

print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n = int(input())
aaa = [tuple(map(int, input().split())) for _ in range(n)]
lo = [min(a) for a in aaa]
hi = [max(a) for a in aaa]
lo.sort(reverse=True)
hi.sort()
ans = sum(lo)

itr = zip(lo, hi)
l, h = next(itr)
ans += h
ans -= l

for l, h in itr:
    if l <= h:
        break
    ans += h
    ans -= l

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

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
_AB = []
for i in range(N):
  a, b = map(int, input().split())
  heapq.heappush(_AB, [a, i, 0])
  heapq.heappush(_AB, [b, i, 1])
AB = []
for i in range(N + 1):
  AB.append(heapq.heappop(_AB))
ans = sum([ab[0] for ab in AB])

A = []
B = []
for ab in AB:
  if ab[2] == 0:
    A.append(ab)
  else:
    B.append(ab)
if len(A) > len(B):
  A, B = B, A
if len(A) == 1:
  ans -= max(A[0][0], B[-1][0] if B[-1][1] != A[0][1] else B[-2][0])
elif len(A) == 2:
  B0 = [b for b in B if b[1] != A[0][1]]
  B1 = [b for b in B if b[1] != A[1][1]]
  if len(B0) == N - 1:
    ans -= max(A[0][0], B1[-1][0])
  else:
    ans -= max(A[1][0], B0[-1][0] if N > 3 else max(B[0][0], B[1][0]))
else:
  ans -= max(A[-1][0], B[-1][0])

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
aaa = [tuple(map(int, input().split())) for _ in range(n)]
lo = [min(a) for a in aaa]
hi = [max(a) for a in aaa]
lo.sort(reverse=True)
hi.sort()
ans = sum(lo)

for l, h in zip(lo, hi):
    if l <= h:
        break
    ans += h
    ans -= l

print(ans)

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC028 C
"""

import itertools
from operator import itemgetter

n = int(input())
abli0 = [tuple(map(int, input().split())) for i in range(n)]
eabli0 = enumerate(abli0)
abli1 = list(map(lambda t: ((t[1][0], t[0], 0), (t[1][1], t[0], 1)), eabli0))
abli = list(itertools.chain.from_iterable(abli1))
abli.sort(key=itemgetter(1))
tmpans0 = sum(map(lambda t: t[0], abli[:n]))
alist = [i for x, i, aorb in abli[:n] if not aorb]
blist = [i for x, i, aorb in abli[:n] if aorb]
flag = bool([i for i in range(n) if i in alist and i in blist])

y, j, arob2 = abli[n]
z, k, arob3 = abli[n+1]
if flag:
    tmpans = tmpans0
else:
    tmpans = 2**62
    for x, i, aorb in abli[:n]:
        if j != i:
            tmp = tmpans0-x+y
        else:
            tmp = tmpans0-x+z
        if tmpans > tmp:
            tmpans = tmp

leftsum = sum(map(lambda x: x[0], abli0))
rightsum = sum(map(lambda x: x[1], abli0))

print(min(leftsum, rightsum, tmpans))

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
_AB = []
for i in range(N):
  a, b = map(int, input().split())
  heapq.heappush(_AB, [a, i, 0])
  heapq.heappush(_AB, [b, i, 1])
AB = []
for i in range(N + 1):
  AB.append(heapq.heappop(_AB))
ans = sum([ab[0] for ab in AB])

cnt = 0
for ab in AB[:-1]:
  if ab[2] == AB[-1][2]:
    cnt += 1
    cmp = ab
if cnt == 1:
  if (len([ab for ab in AB if ab[1] == cmp[1]]) == 1 and len([ab for ab in AB if ab[1] == AB[-1][1]]) == 2):
    ans -= max(cmp[0], AB[-2][0] if AB[-2][1] != AB[-1][1] or N == 2 else AB[-3][0])
  else:
    ans -= AB[-1][0]
else:
  ans -= AB[-1][0]

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
_AB = []
for i in range(N):
  a, b = map(int, input().split())
  heapq.heappush(_AB, [a, i, 0])
  heapq.heappush(_AB, [b, i, 1])
AB = []
for i in range(N + 1):
  AB.append(heapq.heappop(_AB))
ans = sum([ab[0] for ab in AB])

cnt = 0
for ab in AB:
  if ab[2] == AB[-1][2]:
    cnt += 1
    cmp = ab
if cnt == 2:
  if (len([ab for ab in AB if ab[1] == cmp[1]]) == 1 and len([ab for ab in AB if ab[1] == AB[-1][1]]) == 2):
    ans -= max(cmp[0], AB[-2][0] if AB[-2][1] != AB[-1][1] or N == 2 else AB[-3][0])
  else:
    ans -= AB[-1][0]
else:
  ans -= AB[-1][0]

print(ans)

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
 
"""
AGC028 C
"""
 
import itertools
 
n = int(input())
abli = [tuple(map(int, input().split())) for i in range(n)]
 
leftsum = sum(map(lambda x: x[0], abli))
rightsum = sum(map(lambda x: x[1], abli))
 
maxminel = max(enumerate(abli), key=lambda x: 10**10*min(x[1])+max(x[1]))
maxminmax = max(abli[maxminel[0]])
del abli[maxminel[0]]
flattenli = list(itertools.chain.from_iterable(abli))
flattenli.sort()
tmpans = sum(flattenli[:n])
if flattenli[n-1] > maxminmax:
    tmpans = tmpans-flattenli[n-1]+maxminmax
 
 
print(min(leftsum, rightsum, tmpans))

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
_AB = []
for i in range(N):
  a, b = map(int, input().split())
  heapq.heappush(_AB, [a, i, 0])
  heapq.heappush(_AB, [b, i, 1])
AB = []
for i in range(N + 1):
  AB.append(heapq.heappop(_AB))
ans = sum([ab[0] for ab in AB])
A = []
B = []
C = []

cnt = 0
for ab in AB[:-1]:
  if ab[2] == AB[-1][2]:
    cnt += 1
    cmp = ab
if cnt == 1:
  if (len([ab for ab in AB if ab[1] == cmp[1]]) == 1 and len([ab for ab in AB if ab[1] == AB[-1][1]]) == 2):
    ans -= max(cmp[0], AB[-2][0] if AB[-2][1] != AB[-1][1] else AB[-3][1])
  else:
    ans -= AB[-1][0]
else:
  ans -= AB[-1][0]

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
_AB = []
for i in range(N):
  a, b = map(int, input().split())
  heapq.heappush(_AB, [a, i, 0])
  heapq.heappush(_AB, [b, i, 1])
AB = []
for i in range(N + 1):
  AB.append(heapq.heappop(_AB))
ans = sum([ab[0] for ab in AB])
A = []
B = []
C = []

cnt = 0
for ab in AB[:-1]:
  if ab[2] == AB[-1][2]:
    cnt += 1
    cmp = ab
if cnt == 1:
  if (not [ab for ab in AB if ab[1] == cmp[1]] and [ab for ab in AB if [ab] == AB[-1][1]]):
    ans -= max(cmp[0], AB[-2][0] if AB[-2][1] != AB[-1][1] else AB[-3][1])
  else:
    ans -= AB[-1][0]
else:
  ans -= AB[-1][0]

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env 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()

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env 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 False in used[0] or False in used[1]:
    pass
else:
    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