Harryxun/stf_run huggingface dataset:
# coding: utf-8
from sys import stdin.readline as input
 
N, M = [int(i) for i in input().split()]
 
plices = [[int(i) for i in input().split()] for _ in range(N)]
 
plices.sort(key = lambda x:x[0])
 
m = 0
cost = 0
 
for i in range(N):
    if m >= M:
        break
    buy = min(M - m, plices[i][1])
    cost += plices[i][0] * buy
    m += buy
 
print(cost)

### FIXED CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline

N, M = [int(i) for i in input().split()]

plices = [[int(i) for i in input().split()] for _ in range(N)]

plices.sort(key = lambda x:x[0])

m = 0
cost = 0

for i in range(N):
    if m >= M:
        break
    buy = min(M - m, plices[i][1])
    cost += plices[i][0] * buy
    m += buy

print(cost)
# coding: utf-8
# Your code here!
import sys
import resource
sys.setrecursionlimit(10 ** 9)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

mm = {}

def popcorn(n):
    n = bin(n)
    return n.count("1")

def f(n):
    n%=popcorn(n)
    return n
    
def nf(n,count):
    if(n == 0):
        return count
    elif(n in mm):
        count += mm[n]-1
        return count
    else:
        n%=popcorn(n)
        return nf(n,count+1)


n = int(input())
a = input()
moto = int(a,2)
for i in range(n-1,0-1,-1):
    if(a[n-1-i] == "0"):
        k=moto+2**i
    else:
        k=moto-2**i
    mo = f(k)
    if(mo in mm):
        print(mm[mo])
        continue
    else:
        count = nf(mo,1)
        print(count)
        mm[mo]=count
        
    
    


### FIXED CODE ###

# coding: utf-8
# Your code h
l,r,d=map(int,input().split())
ans=0
for i in range(l,r+1):
    ans += i%d == 0
    
print(ans)
from collections import deque
import sys
sys.setrecursionlimit(300000)

N, M, K = map(int, input().split())
A = deque(map(int, input().split()))
B = deque(map(int, input().split()))


def calc(k, n):
    if k > K:
        return n - 1
    else:
        if len(A) and len(B):
            a = A.popleft()
            na = calc(k+a, n+1)
            A.appendleft(a)
            b = B.popleft()
            nb = calc(k+b, n+1)
            B.appendleft(b)
            return max(na, nb)
        elif len(A):
            a = A.popleft()
            na = calc(k + a, n + 1)
            A.appendleft(a)
            return na
        elif len(B):
            b = B.popleft()
            nb = calc(k + b, n + 1)
            B.appendleft(b)
            return nb
        else:
            return n


print(calc(0, 0))


### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

sumA, sumB = [0], [0]
sa, sb = 0, 0
for a in A:
    sa += a
    sumA.append(sa)
for b in B:
    sb += b
    sumB.append(sb)


n_max = 0
nb_max = M
for na in range(0, N+1):
    for nb in range(nb_max, -1, -1):
        k = sumA[na] + sumB[nb]
        if k <= K:
            n = na + nb
            n_max = max(n_max, n)
            nb_max = nb
            break
print(n_max)
print len(set(input().split()))

### FIXED CODE ###

print(len(set(input().split())))
print(sum(list(input())))

### FIXED CODE ###

a=input()
b=0
for i in range(6):
    if int(a[i])==1:
        b+=1
print(b)
import numpy as np

n,m = map(int,input().split())
h = list(map(int,input().split()))

data = np.zeros((n,n))

for i in range(m):
    a,b = map(int,input().split())
    data[a-1,b-1],data[b-1,a-1] = 1,1

#print(data)
ans = 0
for i in range(n):
    ca = 1
    for k,j in enumerate(data[i]):
        if j == 1:
            if h[i]<=h[k]:
                ca = 0
    ans += ca

print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
h = list(map(int,input().split()))

data = [0]*n
#print(h)
#print(data)
for i in range(m):
    a,b = map(int,input().split())
    k = max(data[a-1],h[b-1])
    l = max(h[a-1],data[b-1])
    data[a-1],data[b-1] =k,l

ans = 0

#print(data)
for i in range(n):
    if h[i] > data[i]:
        ans += 1

print(ans)
n=int(input())
s=[input() for i in range(n)]
m=int(input())
t=[input() for j in range(m)]
for i in range(n):
    result=s.count(s[i])-t.count(s[i])
print(max(o,result))


### FIXED CODE ###

n=int(input())
s=[input() for _ in range(n)]
m=int(input())
t=[input() for _ in range(m)]
result=0
for i in set(s):
    result=max(result,s.count(i)-t.count(i))
print(result)
x=int(input())

if 400<=x and x<=599:
    print(8)
elif:
    600<=x and x<=799:
    print(7)
elif:
    800<=x and x<=999:
    print(6)
elif:
    1000<=x and x<=1199:
    print(5)
elif:
    1200<=x and x<=1399:
    print(4)
elif:
    1400<=x and x<=1599:
    print(3)
elif:
    1600<=x and x<=1799:
    print(2)
elif:
    1800<=x and x<=1999:
    print(1)    

### FIXED CODE ###

x=int(input())

if 400<=x and x<=599:
    print(8)
elif 600<=x and x<=799:
    print(7)
elif 800<=x and x<=999:
    print(6)
elif 1000<=x and x<=1199:
    print(5)
elif 1200<=x and x<=1399:
    print(4)
elif 1400<=x and x<=1599:
    print(3)
elif 1600<=x and x<=1799:
    print(2)
elif 1800<=x and x<=1999:
    print(1)
h,w = map(int, input().split())
s = [list(input().split()) for _ in range(h)]
al = list("ABCDEFGHIJ")
i = -1
for v in s:
  i+=1
  if "snuke" in v:
    print(al[s[i].index("snuke")]+str(i+1))
    exit()

### FIXED CODE ###

h,w = map(int, input().split())
s = [list(input().split()) for _ in range(h)]
i = 0
65
for v in s:
  i+=1
  if "snuke" in v:
    print(chr(v.index("snuke")+65)+str(i))
import numpy as np
L, R = map(int, input().split(" "))
arr = np.array(np.arange(L, R+1))
mod_list = []

if (0 in (arr % 2019)) or (0 in arr):
  print(0)
else:
  for i in arr:
    for j in arr[arr != i]:
      mod_list.append(((i * j) % 2019))
      
  print(min(mod_list))

### FIXED CODE ###

import numpy as np

L, R = map(int, input().split(" "))
#L, R = 2020, 4000000000
if R - L > 2019:
    print(0)
else:
    arr = np.array(np.arange(L, R+1))
    mod_list = []
    min_mod_list = []
    
    if (0 in (arr % 2019)) or (0 in arr):
        print(0)
    else:
    
        for i in arr:
            mod_list = []
            index_ = np.where(arr==i)
            if i == arr[-1]:
                break
            
            for j in arr[int(index_[0])+1:]:
                mod_list.append((i * j) % 2019)
     
            min_mod_list.append(min(mod_list))
            if min(mod_list) == 0:
                break
    
    
        print(min(min_mod_list))
import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
bc=[]
for i in range(m):
    b,c=map(int,input().split())
    bc.append([b,c])
bc.sort(key=lambda x:x[1],reverse=True)
x=[0]*(m+3)
for i in range(m):
    x[i+1]=min(bisect.bisect_left(a,bc[i][1]), bc[i][0])+x[i]
    for j in range(x[i],x[i+1]):
        a[j]=bc[i][1]


print(sum(a))


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
l=[]
for i in range(n):
    l.append([1,a[i]])
for i in range(m):
    l.append(list(map(int,input().split())))
l.sort(key=lambda x:x[1], reverse=True)
c=0
ans=0
for i in range(n+m):
    ans+=l[i][1]*l[i][0]
    c+=l[i][0]
    if c>n:
        ans-=l[i][1]*(c-n)
        break
print(ans)
n,m=map(int,input().split())
bridge=[[] for i in range(m)]
iland=[[i+1] for i in range(n)]
for i in range(m):
    bridge[i]=list(map(int,input().split()))
ans=[0 for i in range(m+1)]
ans[0]=int((n-1)*n/2)
k=1
for i in reversed(bridge):
    ans[k]=ans[k-1]
    for j in range(i[0]+1):
        if i[0] in iland[j]:
            temp=j
            break
    for j in range(i[1]+1):
        if i[1] in iland[j]:
            if temp!=j:
                ans[k]=ans[k-1]-len(iland[j])*len(iland[temp])
                iland[temp].extend(iland[j])
                del iland[j]
                break
    if ans[k]==0:
        ans[k:]=[0 for l in range(m-k)]
        break
    k+=1
for i in range(m):
    print(ans[m-1-i])

### FIXED CODE ###

n,m=map(int,input().split())
bridge=[[] for i in range(m)]
leader=[i for i in range(n+1)]
member=[1 for i in range(n+1)]
for i in range(m):
    bridge[i]=list(map(int,input().split()))
ans=[0 for i in range(m+1)]
ans[0]=int((n-1)*n/2)
k=1
for i in reversed(bridge):
    le0=leader[i[0]]
    le1=leader[i[1]]
    while le0!=leader[le0]:
        le0=leader[le0]
        leader[i[0]]=le0
        
    while le1!=leader[le1]:
        le1=leader[le1]
        leader[i[1]]=le1
        
    if le0!=le1:
        ans[k]=ans[k-1]-member[le0]*member[le1]
        if member[le0]>=member[le1]:
            member[le0]+=member[le1]
            leader[le1]=le0
        else:
            member[le1]+=member[le0]
            leader[le0]=le1
    else:
        ans[k]=ans[k-1]
    if ans[k]==0:
        ans[k:]=[0 for l in range(m-k)]
        break
    k+=1
for i in range(m):
    print(ans[m-1-i])
from operator import itemgetter

n = int(input())
e = [[i for i in input().split()] for j in range(n)]
for i in range(n):
    e(i).append(i)
restaurant = sorted(e,key=itemgetter(1),reverse=True)
restaurant.sort(key=itemgetter(0))

for i in range(n):
    print(restaurant[i][2]+1)
    

### FIXED CODE ###

n = int(input())
a= []
for i in range(n):
	city, score = input().split()
	score = int(score)
	a.append((city, score, i+1))
a.sort(key=lambda k : (k[0], -k[1]))
for i in range(n):
	print(a[i][2])
s=list(str(input()))
q=int(input())
now = 0
for _ in range(q):
  lis = list(map(str,input().split()))
  if int(lis[0]) == 1:
    now = (now+1)%2
  else:
    if (int(lis[1])+now)%2 == 1:
      s.insert(0,lis[2])
    else:
      s.append(lis[2])
if now ==0:
  for i in range(len(s)):
    print(s[i],end="")
else:
  for i in range(len(s)):
    print(s[-i-1],end="")
    
  


### FIXED CODE ###

s =str(input())
if "A" not in s or "B" not in s:
  print("No")
else:
  print("Yes")
if abs(a) <= abs(b) and abs(c) <= abs(d):
    print(b*d)
elif abs(a) >= abs(b) and abs(c) <= abs(d):
    print(b*c)
elif abs(a) <= abs(b) and abs(c) >= abs(d):
    print(a*d)
elif abs(a) >= abs(b) and abs(c) >= abs(d):
    print(a*c)

### FIXED CODE ###

x= int(input())
if x==1:
    print('0')
elif x==0:
    print('1')
a, b, c  = map(int, input().split())

if A<=c and c<=b:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a, b, c  = map(int, input().split())

if a<=c and c<=b:
    print("Yes")
else:
    print("No")
a,b,k=[int(x) for x in input().aplit()]

if(k-a>0):
  print(k-a,b)
elif a+b-k>0:
  print(0,a+b-k)
else:
  print(0,0)

### FIXED CODE ###

a,b,k=[int(x) for x in input().split()]

if(a-k>0):
  print(a-k,b)
elif a+b-k>0:
  print(0,a+b-k)
else:
  print(0,0)
s=int(input())
print(2*min(s.count(0),mins.count(1)))

### FIXED CODE ###

s=input();print(min(s.count("0"),s.count("1"))*2)
def f(n, k):
  num_bit = 3 - bin(k).count('1')
  c = [0, 0, 1, 3]
  return 3**n - num_bit*2**n + c[num_bit]

# k = 0:(), 1:(3), 2(5), 3:(3, 5), 4:(7), 5:(3, 7), 6:(5, 7), 7:(3, 5, 7)
def solve(N, k=0):
  n = len(N)
  num_used = bin(k).count('1')
  if n==0 and num_used==3:
    return 1
  elif n==0 or n+num_used<3:
    return 0
  else:
    a = int(N[0])
    if a > 7:
      return sum([f(i, 0) for i in range(3, n+1)])
    elif a == 7:
      return f(n-1, k|2) + f(n-1, k|1) + solve(N[1:], k|4)
    elif a > 5:
      return f(n-1, k|2) + f(n-1, k|1)
    elif a == 5:
      return f(n-1, k|1) + solve(N[1:], k|2)
    elif a > 3:
      return f(n-1, k|1)
    elif a == 3:
      return solve(N[1:], k|1)
    elif a > 0:
      return 0

N = input()
base = sum([f(i, 0) for i in range(3, len(N))])
print(solve(N) + base)

### FIXED CODE ###

def f(n, k):
  num_bit = 3 - bin(k).count('1')
  c = [0, 0, 1, 3]
  return 3**n - num_bit*2**n + c[num_bit]

# k = 0:(), 1:(3), 2(5), 3:(3, 5), 4:(7), 5:(3, 7), 6:(5, 7), 7:(3, 5, 7)
def solve(N, k=0):
  n = len(N)
  num_used = bin(k).count('1')
  if n==0 and num_used==3:
    return 1
  elif n==0 or n+num_used<3:
    return 0
  else:
    a = int(N[0])
    if a > 7:
      return f(n-1, k|1) + f(n-1, k|2) + f(n-1, k|4)
    elif a == 7:
      return f(n-1, k|2) + f(n-1, k|1) + solve(N[1:], k|4)
    elif a > 5:
      return f(n-1, k|2) + f(n-1, k|1)
    elif a == 5:
      return f(n-1, k|1) + solve(N[1:], k|2)
    elif a > 3:
      return f(n-1, k|1)
    elif a == 3:
      return solve(N[1:], k|1)
    else:
      return 0

N = input()
base = sum([f(i, 0) for i in range(3, len(N))])
print(solve(N) + base)
n = int(input())
a = list(map(int,input().split()))
b = sorted(a)
for i in range(n):
    if b[int(n/2)+1] <= a[i]:
        print(b[int(n/2)-1])
    else:
        print(b[int(n/2)])

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = sorted(a)
for i in range(n):
    if b[int(n/2)] <= a[i]:
        print(b[int(n/2)-1])
    else:
        print(b[int(n/2)])
N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range (0, N):
	if A[i] == 0:
		ans = 0
        break
	else:
		ans *= A[i]

if ans > 10 ** 18:
	print(-1)
else:
	print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range (0, N):
	if A[i] == 0:
		ans = 0
		break
	else:
		if ans > 0:
			ans *= A[i]
		if ans > 10 ** 18:
			ans = -1

print(ans)
a,b=map(int,input().split())
pl = a+b
di = a-b
mu = a*b
if pl>di and pl>mu:
    print(pl)
elif di>pl and di>mu:
    print(di)
else mu>di and mu>pl:
    print(mu)

### FIXED CODE ###

a,b=map(int,input().split())
pl = a+b
di = a-b
mu = a*b
if pl>=di and pl>=mu:
    print(pl)
elif di>=pl and di>=mu:
    print(di)
else:
    print(mu)
import fractions
import AtCoderUtils
Utils = AtCoderUtils.ACUtils()


ABCD = list(map(int, input().split()))

A = ABCD[0]
B = ABCD[1]
C = ABCD[2]
D = ABCD[3]


# def lcm(x, y):
#     return (x * y) // fractions.gcd(x, y)


# def floor(a, b):
#   # return int((a - a%b)/b)
#   return a//b
# def gcd(a, b):
#   while b != 0:
#       a, b = b, a % b
#   return a
# def lcm(a, b):
#   return floor((a * b), gcd(a, b))

firstC = Utils.floor((A-1),C)
firstD = Utils.floor((A-1),D)
firstCD = Utils.floor((A-1),Utils.lcm(C,D))

# if A%lcm(C,D) ==0 and firstCD > 0:
#     firstCD -= 1

endC = Utils.floor(B,C)
endD = Utils.floor(B,D)
endCD = Utils.floor(B,Utils.lcm(C,D))

End = B-endC-firstD + endCD
First = (A-1) - firstC - firstD + firstCD



thereC = endC - firstC
thereD = endD - firstD
thereCD = endCD - firstCD

NoP = thereC+thereD - thereCD

# print(thereC)
# print(thereD)
# print(thereCD)
# print(NoP)
print((B-A+1)-NoP)
# print(End-First)









### FIXED CODE ###

import fractions

ABCD = list(map(int, input().split()))

A = ABCD[0]
B = ABCD[1]
C = ABCD[2]
D = ABCD[3]


# def lcm(x, y):
#     return (x * y) // fractions.gcd(x, y)


def floor(a, b):
  # return int((a - a%b)/b)
  return a//b
def gcd(a, b):
  while b != 0:
      a, b = b, a % b
  return a
def lcm(a, b):
  return floor((a * b), gcd(a, b))

firstC = floor((A-1),C)
firstD = floor((A-1),D)
firstCD = floor((A-1),lcm(C,D))

# if A%lcm(C,D) ==0 and firstCD > 0:
#     firstCD -= 1

endC = floor(B,C)
endD = floor(B,D)
endCD = floor(B,lcm(C,D))

End = B-endC-firstD + endCD
First = (A-1) - firstC - firstD + firstCD



thereC = endC - firstC
thereD = endD - firstD
thereCD = endCD - firstCD

NoP = thereC+thereD - thereCD

# print(thereC)
# print(thereD)
# print(thereCD)
# print(NoP)
print((B-A+1)-NoP)
# print(End-First)
c = int(input())

a = int(input())

print(int(a*c/2))

### FIXED CODE ###

c, a, b= list(map(int,input().split()))

print(int(a*c/2))
x = int(input())
a = 1
b = 0
A = []

while True:
    if A[-1] > 10 ** 9:
        break
    A.append(a ** 5 - x)
    a = a + 1

while True:
    if b ** 5 in A:
        break
    elif -b ** 5 in A:
        b = -b
        break
    b = b + 1

a = int((x + b ** 5) ** 0.2)

print(a, b)

### FIXED CODE ###

x = int(input())
a = 2
b = 0
A = []
A.append(1 ** 5 - x)

while True:
    if (a + 1) ** 5 - a ** 5 > 10 ** 10:
        break
    A.append(a ** 5 - x)
    a = a + 1

while True:
    if b ** 5 in A:
        break
    elif -b ** 5 in A:
        b = -b
        break
    b = b + 1

a = int((x + b ** 5) ** 0.2)

print(a, b)
import heapq
def main():
    n,m=map(int, input().split()) 
    a = [map(lambda x: int(x)*(-1), input().split())] 
    heapq.heapify(a)

    for i in range(m):
        tmp_min = heapq.heappop(a)
        heapq.heappush(a, -1*(-tmp_min//2))
    print(-sum(a))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import heapq
def main():
    n,m=map(int, input().split()) 
    a = list(map(lambda x: int(x)*(-1), input().split())) 
    heapq.heapify(a)

    for i in range(m):
        tmp_min = heapq.heappop(a)
        heapq.heappush(a, -1*(-tmp_min//2))
    print(-sum(a))

if __name__ == '__main__':
    main()
n = input()
l = [int(i) for i in input().split()]
print(' '.join([str(min(l)),str(max(l)),str(sum(l))])

### FIXED CODE ###

n = input()
l = [int(i) for i in input().split()]
print(' '.join([str(min(l)),str(max(l)),str(sum(l))]))
A,B,C,X,Y = map(int, input().split())

l = []

#パターン１ AとBだけ作るとき
price1 = A * X + B * Y
l.append(price1)

#パターン2 AB分割とあまり調整
if X > Y:
    if A < C/2:
        price2 = 2 * Y * C + A * abs(X-Y)
        l.append(price2)
    else:
        price3 = 2 * Y * C + C * abs(X-Y) * 2
        l.append(price3)
elif X < Y:
    if B < C/2:
        price4 = 2 * X * C + B * abs(Y-X)
        l.append(price4)
    else:
        price5 = 2 * X * C + C * abs(Y-X) * 2
        l.append(price5)

elif x == Y:
    price6 = 2 * X * C
    l.append(price6)


print(min(l))


### FIXED CODE ###

A,B,C,X,Y = map(int, input().split())

l = []

#パターン１ AとBだけ作るとき
price1 = A * X + B * Y
l.append(price1)

#パターン2 AB分割とあまり調整
if X > Y:
    if A < 2*C:
        price2 = 2 * Y * C + A * abs(X-Y)
        l.append(price2)
    else:
        price3 = 2 * Y * C + C * abs(X-Y) * 2
        l.append(price3)
elif X < Y:
    if B < 2*C:
        price4 = 2 * X * C + B * abs(Y-X)
        l.append(price4)
    else:
        price5 = 2 * X * C + C * abs(Y-X) * 2
        l.append(price5)

else:
    price6 = 2 * X * C
    l.append(price6)


print(min(l))
N=int(input())
A=list(map(int,input().split()))
S=0
B=[0]*10**5
for i in A:
    S+=i
    B[i]+=1  #Bは要素数管理
Q=int(input())
C=[list(map(int,input().split())) for i in range(Q)]
for i in range(Q):
    S=S+(C[i][1]-C[i][0])*B[C[i][0]]
    B[C[i][1]]=B[C[i][0]]+B[C[i][1]]
    B[C[i][0]]=0
    print(S)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
S=0
B=[0]*(10**5+1)
for i in A:
    S+=i
    B[i]+=1  #Bは要素数管理
Q=int(input())
C=[list(map(int,input().split())) for i in range(Q)]
for i in range(Q):
    S=S+(C[i][1]-C[i][0])*B[C[i][0]]
    B[C[i][1]]=B[C[i][0]]+B[C[i][1]]
    B[C[i][0]]=0
    print(S)
def solve(a, b, c, d, e, f):
    S = set()
    for x in range(0, f, 100*a):
        for y in range(0, f, 100*b):
            z = x + y
            if 0 < z <= f:
                S.add(z)
    T = set()
    for x in range(0, f, c):
        for y in range(0, f, d):
            z = x + y
            if z <= f:
                T.add(z)
    threshold = e / (100 + e)
    best = 0
    solution = None
    for x in S:
        for y in T:
            z = x + y
            cur = y / z
            if (best < cur <= threshold) and (z <= f):
                best = cur
                solution = (z, y)
    return "%d %d" % solution

a, b, c, d, e, f = map(int, input().split())
print(solve(a, b, c, d, e, f))

### FIXED CODE ###

EPS = 1E-8
def solve(a, b, c, d, e, f):
    threshold = e / (100 + e) + EPS
    best = -1
    for x in range(0, f+1, 100*a):
        for y in range(x, f+1, 100*b):
            if y == 0:
                continue
            for z in range(y, f+1, c):
                for w in range(z, f+1, d):
                    p = w - y
                    cur = p / w
                    if best < cur <= threshold:
                        best = cur
                        solution = (w, p)
    return "%d %d" % solution

a, b, c, d, e, f = map(int, input().split())
print(solve(a, b, c, d, e, f))
a = input()
b = input()
c = len(a)
a_list = list(a)
b_list = list(b)
for i in range(101):
  tmp = a_list[0]
  for j in range(c-1):
    a_list[j] = a_list[j+1]
  a_list[c-1] = tmp
  if a_list == b_list:
    print("Yes")
    exit()
print("No")


### FIXED CODE ###

a,b,c = map(int, input().split())
d = abs(a-b)
e = abs(a-c)
g = abs(b-c)
if d >= e and d >= g:
  print(e+g)
elif e >= d and e >= g:
  print(d+g)
else:
  print(d+e)
from collections import defaultdict
def main():
    N = int(input())
    depth = [0 for _ in range(N)]
    def dfs(v,p,d):
        depth[v] = d
        for u in tree[v]:
            if u[0] == p:continue
            dfs(u[0],v,d+u[1])
    tree = defaultdict(list)
    for _ in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        tree[a] += [[b,c]]
        tree[b] += [[a,c]]
    Q,K = map(int,input().split())
    K -= 1
    dfs(K,-1,0)
    for _ in range(Q):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        ans = depth[x]+depth[y]
        print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import defaultdict,deque
def main():
    N = int(input())
    depth = [-1 for _ in range(N)]
    tree = defaultdict(list)
    for _ in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        tree[a] += [[b,c]]
        tree[b] += [[a,c]]
    Q,K = map(int,input().split())
    K -= 1
    stack = deque([K])
    depth[K] = 0
    while stack:
        v = stack.popleft()
        for e in tree[v]:
            u,c = e
            if u == K:
                continue
            if depth[u] == -1:
                stack.appendleft(u)
                depth[u] = depth[v] + c

    for _ in range(Q):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        ans = depth[x]+depth[y]
        print(ans)

if __name__ == "__main__":
    main()
def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n-1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  # swap smaller one.
        a_list.append(a)
        b_list.append(b)
    c_list = []
    c_list = list(map(int, input().split()))
    lr_list = []
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    total = 0
    c_list = sorted(c_list, reverse=True) # Because maximum number is not selected at all.
    import itertools
    current_max = 0
    current_list = []
    for new_list in itertools.permutations(c_list, n):
        total = 0
        for i in range(n - 1):
            total += min(new_list[a_list[i]-1], new_list[b_list[i]-1])
        if total >= current_max:
            current_max = total
            current_list = new_list

    return f"{current_max}\n" + " ".join(map(str, current_list))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

### FIXED CODE ###


def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n - 1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  # swap smaller one.
        a_list.append(a)
        b_list.append(b)
    c_list = []
    c_list = list(map(int, input().split()))
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    edge = [[] for i in range(n)]
    for i in range(len(a_list)):
        a, b = a_list[i] - 1, b_list[i] - 1  # convert to 0 based index.
        edge[a].append(b)
        edge[b].append(a)
    c_list_new = sorted(c_list, reverse=True)

    value = sum(c_list_new[1:])

    vertices = [None] * n
    vertices[0] = c_list_new.pop(0)

    search_path = []
    search_path.extend(edge[0])

    while search_path:
        node = search_path.pop(0)
        if vertices[node] is None:
            vertices[node] = c_list_new.pop(0)
            search_path.extend(edge[node])
    return str(value) + '\n' + ' '.join(map(str, vertices))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()