Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
 = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

if sum(a) < sum(b):
    print("-1")
    exit()
yobun_sum = []

for i in range(N):
    if a[i] > b[i]:
        yobun_sum.append(a[i]-b[i])

yobun_sum.sort()
yobun_sum.reverse()

yobun_cum_sum=[]
cum_sum=0
for i in yobun_sum:
    cum_sum+=i
    yobun_cum_sum.append(cum_sum)

yobun_ind = 0
lack_num=0
use_first=False

for i in range(N):
    if a[i] < b[i]:
        use_first=True
        lack_num+=1
        lack = abs(a[i] - b[i])
        if yobun_cum_sum[yobun_ind] >= lack: # can pay
            yobun_cum_sum[yobun_ind] -= lack
        else: # can't pay
            yobun_cum_sum[yobun_ind+1] -= lack - yobun_cum_sum[yobun_ind]
            yobun_cum_sum[yobun_ind] =0
            yobun_ind+=1

if use_first:
    yobun_ind+=1

print(yobun_ind+lack_num)

Fixed submission:
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

if sum(a) < sum(b):
    print("-1")
    exit()
yobun_sum = []

for i in range(N):
    if a[i] > b[i]:
        yobun_sum.append(a[i]-b[i])

yobun_sum.sort()
yobun_sum.reverse()
yobun_cum_sum=[]
cum_sum=0
for i in yobun_sum:
    cum_sum+=i
    yobun_cum_sum.append(cum_sum)

lack_num=0
lack_sum=0

for i in range(N):
    if a[i] < b[i]:
        lack_num+=1
        lack = abs(a[i] - b[i])
        lack_sum+=lack

for i in range(len(yobun_cum_sum)):
    if yobun_cum_sum[i] >= lack_sum:
        break

if lack_sum==0:
    print(0)
else:
    print(lack_num+i+1)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))

#def cost(i,j):
#    return abs(h[i] - h[j])

dp=[10**9]*n
dp[0]=0

for i in range(1,n):
    for j in range(i-k,i):
        if j>=0:
            cst = dp[j]+abs(h[i] - h[j])
            if dp[i] > cst:
                dp[i]=cst

print(dp[n-1])

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))

def cost(i,j):
    return abs(h[i] - h[j])

dp=[10**9]*n
dp[0]=0

for i in range(1,n):
    for j in range(i-k,i):
        if j>=0:
            cst = dp[j]+cost(j,i)
            if dp[i] > cst:
                dp[i]=cst

print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))

def cost(i,j):
    return abs(h[i] - h[j])

dp=[10**9]*n
dp[0]=0

for i in range(1,n):
#    mn=10*9
    for j in range(i-k,i):
        if j>=0:
            cst = dp[j]+cost(j,i)
            if dp[i] > cst:
                dp[i]=cst
#    dp[i]=mn

print(dp[n-1])

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))

def cost(i,j):
    return abs(h[i] - h[j])

dp=[10**9]*n
dp[0]=0

for i in range(1,n):
    for j in range(i-k,i):
        if j>=0:
            cst = dp[j]+cost(j,i)
            if dp[i] > cst:
                dp[i]=cst

print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))
import heapq

def cost(i,j):
    return abs(h[i] - h[j])

dp=[0]*n
dp[0]=0

for i in range(1,n):
    lst=[]

    for j in range(i-k,i):
        if j>=0:
            heapq.heappush(lst, dp[j]+cost(j,i))
    dp[i]=heapq.heappop(lst)

print(dp[n-1])

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))

def cost(i,j):
    return abs(h[i] - h[j])

dp=[10**9]*n
dp[0]=0

for i in range(1,n):
    for j in range(i-k,i):
        if j>=0:
            cst = dp[j]+cost(j,i)
            if dp[i] > cst:
                dp[i]=cst

print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))

def cost(i,j):
    return abs(h[i] - h[j])

dp=[0]*n
dp[0]=0

for i in range(1,n):
    lst=[]

    for j in range(i-k,i):
        if j>=0:
            lst.append(dp[j]+cost(j,i))
    dp[i]=min(lst)

print(dp[n-1])

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))

def cost(i,j):
    return abs(h[i] - h[j])

dp=[10**9]*n
dp[0]=0

for i in range(1,n):
    for j in range(i-k,i):
        if j>=0:
            cst = dp[j]+cost(j,i)
            if dp[i] > cst:
                dp[i]=cst

print(dp[n-1])
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = []
for _ in range(N):
    D = list(map(int, input().split()))
    S.append(D)

import numpy as np
dp=np.zeros((N+1,3))

for i in range(1,N+1):
    for j in range(3):
        for k in range(3):
            if j != k:

                dp[i][j] = max(dp[i-1][k] + S[i-1][j],dp[i][j])
                #happy =  dp[i-1][k] + S[i-1][j]
                #if dp[i][j] < happy:
                #    dp[i][j] = happy

print(int(max(dp[N])))

Fixed submission:
N = int(input())
S = []
for _ in range(N):
    D = list(map(int, input().split()))
    S.append(D)

import numpy as np
#dp=np.zeros((N+1,3))

dp = [[0 for _ in range(3)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(3):
        for k in range(3):
            if j != k:
                happy =  dp[i-1][k] + S[i-1][j]
                if dp[i][j] < happy:
                    dp[i][j] = happy

print(int(max(dp[N])))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = []
for _ in range(N):
    D = list(map(int, input().split()))
    S.append(D)

import numpy as np
dp=np.zeros((N+1,3))

for i in range(1,N+1):
    for j in range(3):
        for k in range(3):
            if j != k:

                dp[i][j] = max(dp[i-1][k] + S[i-1][j],dp[i][j])
                #happy =  dp[i-1][k] + S[i-1][j]
                #if dp[i][j] < happy:
                #    dp[i][j] = happy

print(int(max(dp[N])))

Fixed submission:
N = int(input())
S = []
for _ in range(N):
    D = list(map(int, input().split()))
    S.append(D)

import numpy as np
#dp=np.zeros((N+1,3))

dp = [[0 for _ in range(3)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(3):
        for k in range(3):
            if j != k:
                happy =  dp[i-1][k] + S[i-1][j]
                if dp[i][j] < happy:
                    dp[i][j] = happy

print(int(max(dp[N])))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = []
for _ in range(N):
    D = list(map(int, input().split()))
    S.append(D)

import numpy as np
dp=np.zeros((N+1,3))

for i in range(1,N+1):
    for j in range(3):
        for k in range(3):
            if j != k:
                happy =  dp[i-1][k] + S[i-1][j]
                if dp[i][j] < happy:
                    dp[i][j] = happy

print(int(max(dp[N])))

Fixed submission:
N = int(input())
S = []
for _ in range(N):
    D = list(map(int, input().split()))
    S.append(D)

import numpy as np
#dp=np.zeros((N+1,3))

dp = [[0 for _ in range(3)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(3):
        for k in range(3):
            if j != k:
                happy =  dp[i-1][k] + S[i-1][j]
                if dp[i][j] < happy:
                    dp[i][j] = happy

print(int(max(dp[N])))
Buggy python submission (verdict: Time Limit Exceeded):
n,w = map(int, input().split())
wv = []
vsum=0
for _ in range(n):
    tmp = list(map(int,input().split()))
    wv.append(tmp)
    vsum += tmp[1]

INF = 1 << 30

dp = [[INF for i in range(vsum+1)] for j in range(n+1)]
dp[0][0]=0

for i in range(1,n+1):
    now_w,now_v =wv[i-1]
    for v in range(vsum+1):
        dp[i][v] = dp[i-1][v]
        if v - now_v >= 0:
            dp[i][v] = min(dp[i][v],dp[i-1][v-now_v] + now_w)

ans=0
for val in range(len(dp[-1])):
    if dp[-1][val] <= w:
        ans=val
print(ans)

Fixed submission:
n,w = map(int, input().split())
wv = []
vsum=0
for _ in range(n):
    tmp = list(map(int,input().split()))
    wv.append(tmp)
    vsum += tmp[1]

dp = [[float("inf") for i in range(vsum+1)] for j in range(n+1)]
dp[0][0]=0

for i in range(1,n+1):
    now_w,now_v =wv[i-1]
    for v in range(vsum+1):
        dp[i][v] = dp[i-1][v]
        if v - now_v >= 0:
            dp[i][v] = min(dp[i][v],dp[i-1][v-now_v] + now_w)

ans=0
for val in range(len(dp[-1])):
    if dp[-1][val] <= w:
        ans=val
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,w = map(int, input().split())
wv = []
for _ in range(n):
    data = list(map(int,input().split()))
    wv.append(data)

dp = [[0 for i in range(w+1)] for j in range(n+1)]

for item in range(n):
    now_w=wv[item][0]
    now_v=wv[item][1]

    for weight in range(w+1):
        ans1=dp[item][weight]
        ans2=-1
        if weight - now_w >= 0:
            ans2=dp[item][weight-now_w]+now_v
        dp[item+1][weight] = max(ans1,ans2)

print(dp[n][w])

Fixed submission:
n,w = map(int, input().split())
wv = []
vsum=0
for _ in range(n):
    tmp = list(map(int,input().split()))
    wv.append(tmp)
    vsum += tmp[1]

dp = [[float("inf") for i in range(vsum+1)] for j in range(n+1)]
dp[0][0]=0

for i in range(1,n+1):
    now_w,now_v =wv[i-1]
    for v in range(vsum+1):
        dp[i][v] = dp[i-1][v]
        if v - now_v >= 0:
            dp[i][v] = min(dp[i][v],dp[i-1][v-now_v] + now_w)

ans=0
for val in range(len(dp[-1])):
    if dp[-1][val] <= w:
        ans=val
print(ans)
Buggy python submission (verdict: Runtime Error):
def divs(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n,p = map(int, input().split())
ans=1
for d in divs(p):
  if pow(d,n)>p:
    break
  if p % pow(d,n)==0:
    ans=d
print(ans)

Fixed submission:
def divs(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n,p = map(int, input().split())
if n>100:
  print(1)
  exit()

ans=1
for d in divs(p):
  if pow(d,n)>p:
    break
  if p % pow(d,n)==0:
    ans=d
print(ans)
Buggy python submission (verdict: Runtime Error):
n,x = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

for i in range(n):
  if a[i] == n:
    ans+=1
    break
  elif a[i] > n:
    break
  else:
    if i!=n(-1):
      ans+=1
      n-=a[i]
print(ans)
    

Fixed submission:
n,x = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans=0
for i in range(n):
  if a[i] == x:
    ans+=1
    break
  elif a[i] > x:
    break
  else:
    if i!=(n-1):
      ans+=1
      x-=a[i]
print(ans)
Buggy python submission (verdict: Runtime Error):
s=input()
k=int(input())
for i in range(len(s)):
        if s[i] != "1":
                not1=i
                break
if k > not1:
        print(s[not1])
else:
        print(1)

Fixed submission:
s=input()
k=int(input())

not1=-1
for i in range(len(s)):
        if s[i] != "1":
                not1=i
                break

if not1==-1:
        print(1)
elif k > not1:
        print(s[not1])
else:
        print(1)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(999999999)
from functools import lru_cache
@lru_cache(maxsize=32)
def solve(cnt,nokori):
    if nokori<6:
        return cnt+nokori

    for six in range(10,-1,-1):
        if 6**six <= nokori:
            break
    for nine in range(10,-1,-1):
        if 9**nine <= nokori:
            break

    res1 = solve(cnt+1,nokori-6**six)
    if nine != 0:
        res2 = solve(cnt+1,nokori-9**nine)
    else:
        res2=10**9

    return min([res1,res2])

print(solve(0,n))

Fixed submission:
n = int(input())

import sys
sys.setrecursionlimit(999999999)
from functools import lru_cache
@lru_cache(maxsize=32)
def solve(cnt,nokori):
    if nokori<6:
        return cnt+nokori

    for six in range(10,-1,-1):
        if 6**six <= nokori:
            break
    for nine in range(10,-1,-1):
        if 9**nine <= nokori:
            break

    res1 = solve(cnt+1,nokori-6**six)
    if nine != 0:
        res2 = solve(cnt+1,nokori-9**nine)
    else:
        res2=10**9

    return min([res1,res2])

print(solve(0,n))

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(999999999)
from functools import lru_cache
@lru_cache(maxsize=32)
def solve(cnt,nokori):
    if nokori<6:
        return cnt+nokori

    for six in range(10,-1,-1):
        if 6**six <= nokori:
            break
    for nine in range(10,-1,-1):
        if 9**nine <= nokori:
            break

    res1 = solve(cnt+1,nokori-6**six)
    if nine != 0:
        res2 = solve(cnt+1,nokori-9**nine)
    else:
        res2=10**9

    return min([res1,res2])

print(solve(0,n))

Fixed submission:
n = int(input())

import sys
sys.setrecursionlimit(999999999)
from functools import lru_cache
@lru_cache(maxsize=32)
def solve(cnt,nokori):
    if nokori<6:
        return cnt+nokori

    for six in range(10,-1,-1):
        if 6**six <= nokori:
            break
    for nine in range(10,-1,-1):
        if 9**nine <= nokori:
            break

    res1 = solve(cnt+1,nokori-6**six)
    if nine != 0:
        res2 = solve(cnt+1,nokori-9**nine)
    else:
        res2=10**9

    return min([res1,res2])

print(solve(0,n))
Buggy python submission (verdict: Runtime Error):
A,B = map(int, input().split())
print(max(A+B,A−B,A*B))

Fixed submission:
A,B = map(int, input().split())
print(max(A+B,A-B,A*B))

Buggy python submission (verdict: Runtime Error):
A,B = map(int, input().split())
print(max([A+B, A−B, A*B]))

Fixed submission:
A,B = map(int, input().split())
print(max(A+B,A-B,A*B))

Buggy python submission (verdict: Runtime Error):
A,B = map(int, input().split())
print(max([A+B, A−B, A×B]))

Fixed submission:
A,B = map(int, input().split())
print(max(A+B,A-B,A*B))
Buggy python submission (verdict: Runtime Error):
a,b,c,k = map(int, input().split())

itr = k//3
amari = k%3

a *= pow(2,itr)
b *= pow(2,itr)
c *= pow(2,itr)

for i in range(amari):
  newa=b+c
  newb=a+c
  newc=b+c
  a,b,c = newa,newb,newc

if abs(a-b) > 10**18:
  print("Unfair")
else:
  print(a-b)

Fixed submission:
a,b,c,k = map(int, input().split())

ans=a-b
if k%2==1:
  ans=b-a
if ans > 10**18:
  print("Unfair")
else:
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
x=int(input())

ans=1
for b in range(x):
    for p in range(2,x):
        if b**p <= x:
            ans=max(ans,b**p)
print(ans)

Fixed submission:
x=int(input())

ans=1
for b in range(x):
    for p in range(2,x):
        if b**p <= x:
            ans=max(ans,b**p)
        else:
            break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
k=int(input())
lis=set()
for i in range(len(s)+1):
    for j in range(i+1,len(s)+1):
        lis.add(s[i:j])
lis=list(lis)
lis.sort()
print(lis[k-1])

Fixed submission:
s=input()
k=int(input())
lis=set()
for i in range(len(s)+1):
    for j in range(i+1,min(i+100,len(s)+1)):
        lis.add(s[i:j])
lis=list(lis)
lis.sort()
print(lis[k-1])

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
k=int(input())
lis=set()
for i in range(len(s)+1):
    for j in range(i+1,len(s)+1):
        lis.add(s[i:j])
lis=list(lis)
lis.sort()
print(lis[k-1])

Fixed submission:
s=input()
k=int(input())
lis=set()
for i in range(len(s)+1):
    for j in range(i+1,min(i+100,len(s)+1)):
        lis.add(s[i:j])
lis=list(lis)
lis.sort()
print(lis[k-1])
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

s=[0]
sm=0
for i in a:
    sm+=i
    s.append(sm)
s.sort()
import collections
c = collections.Counter(s)
from math import factorial
def ncr(n,r):
    return factorial(n) / factorial(r) / factorial(n - r)
ans=0
for v in c.values():
    if v>1:
        ans+=ncr(v,2)

print(int(ans))

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

s=[0]
sm=0
for i in a:
    sm+=i
    s.append(sm)
s.sort()
import collections
c = collections.Counter(s)

ans=0
for v in c.values():
    if v>1:
        ans+=v*(v-1)//2

print(int(ans))

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

s=[0]
sm=0
for i in a:
    sm+=i
    s.append(sm)
s.sort()
import collections
c = collections.Counter(s)
from math import factorial
def ncr(n,r):
    return factorial(n) / factorial(r) / factorial(n - r)
ans=0
for v in c.values():
    if v>1:
        ans+=ncr(v,2)

print(int(ans))

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

s=[0]
sm=0
for i in a:
    sm+=i
    s.append(sm)
s.sort()
import collections
c = collections.Counter(s)

ans=0
for v in c.values():
    if v>1:
        ans+=v*(v-1)//2

print(int(ans))
Buggy python submission (verdict: Runtime Error):
def isp(str): return True if str == str[::-1] else False
a=int(input())
b=int(input())
ans=0
for i in range(a,b+1):
  i_s=str(i)
  if isp:
    ans+=1
    
print(ans)


Fixed submission:
def isp(str): return True if str == str[::-1] else False
a,b= map(int, input().split())
ans=0
for i in range(a,b+1):
  i_s=str(i)
  if isp(i_s):
    ans+=1

print(ans)
Buggy python submission (verdict: Runtime Error):
x,y = map(int, input().split())
if x%y==0
  print(-1)
else:
  print(x)

Fixed submission:
x,y = map(int, input().split())
if x%y==0:
  print(-1)
else:
  print(x)
Buggy python submission (verdict: Runtime Error):
n=int(input())
def ceil(a,b):
    ret = -(-a//b)
    if ret%2==0:
        return ret
    else:
        return ret+1

print(0)
first=input()
if first=="Vacant":
    exit()

l=0
r=n

while abs(l-r)>5:
    nxt = ceil(l+r,2)
    print("l==",l,"r==",r)
    print(nxt)
    ans=input()
    if ans=="Vacant":
        exit()
    if ans==first:
        l=nxt
    else:
        r=nxt


for i in range(l,r):
    print(i)
    ans=input()
    if ans=="Vacant":
        exit()

Fixed submission:
n=int(input())
def ceil(a,b):
    ret = -(-a//b)
    if ret%2==0:
        return ret
    else:
        return ret+1

print(0)
first=input()
if first=="Vacant":
    exit()

l=0
r=n

while abs(l-r)>5:
    nxt = ceil(l+r,2)
    print(nxt)
    ans=input()
    if ans=="Vacant":
        exit()
    if ans==first:
        l=nxt
    else:
        r=nxt


for i in range(l,r):
    print(i)
    ans=input()
    if ans=="Vacant":
        exit()

Buggy python submission (verdict: Runtime Error):
n=int(input())
def ceil(a,b):
    ret = -(-a//b)
    if ret%2==0:
        return ret
    else:
        return ret+1

print(0)
first=input()
if first=="Vacant":
    exit()

l=0
r=n

while abs(l-r)>3:
    nxt = ceil(l+r,2)
    print("l==",l,"r==",r)
    print(nxt)
    ans=input()
    if ans=="Vacant":
        exit()
    if ans==first:
        l=nxt
    else:
        r=nxt


for i in range(l,r):
    print(i)
    ans=input()
    if ans=="Vacant":
        exit()

Fixed submission:
n=int(input())
def ceil(a,b):
    ret = -(-a//b)
    if ret%2==0:
        return ret
    else:
        return ret+1

print(0)
first=input()
if first=="Vacant":
    exit()

l=0
r=n

while abs(l-r)>5:
    nxt = ceil(l+r,2)
    print(nxt)
    ans=input()
    if ans=="Vacant":
        exit()
    if ans==first:
        l=nxt
    else:
        r=nxt


for i in range(l,r):
    print(i)
    ans=input()
    if ans=="Vacant":
        exit()
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int, input().split())
a = list(map(int, input().split()))
xy=[list(map(int,input().split())) for i in range(m)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())

uf = UnionFind(n)
for x,y in xy:
    uf.union(x,y)

g=uf.group_count()

if g==1:
    print(0)
    exit()

if n<(g-1)*2:
    print("Impossible")
    exit()

ans=0

all_costs=[]
for r in uf.roots():
    costs=[]
    for mem in uf.members(r):
        costs.append(a[mem])
    costs.sort()
    ans+=costs[0]
    all_costs.extend(costs[1:])

all_costs.sort()
ans+=sum(all_costs[:(g-2)])

print(ans)

Fixed submission:
n,m = map(int, input().split())
a = list(map(int, input().split()))
xy=[list(map(int,input().split())) for i in range(m)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())

uf = UnionFind(n)
for x,y in xy:
    uf.union(x,y)

g=uf.group_count()

if g==1:
    print(0)
    exit()

if n<(g-1)*2:
    print("Impossible")
    exit()

ans=0
all_costs=[]

from collections import defaultdict
costs=defaultdict(list)
for i in range(n):
    costs[uf.find(i)].append(a[i])

for k,v in costs.items():
    v.sort()
    ans+=v[0]
    all_costs.extend(v[1:])

all_costs.sort()
ans+=sum(all_costs[:(g-2)])

print(ans)