Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7


S = list(input())
x, y = map(int, input().split())

N = 8010

X = [0]
Y = [0]
flag = True
for s in S:
    if s == 'F':
        if flag:
            X[-1] += 1
        else:
            Y[-1] += 1
    else:
        if flag:
            if Y[-1] != 0:
                Y.append(0)
        else:
            if X[-1] != 0:
                X.append(0)
        flag = not flag

dp = [[False] * (2 * N) for _ in range(len(X))]
if S[0] == 'F':
    dp[0][X[0] + N] = True
else:
    dp[0][X[0] + N] = True
    dp[0][-X[0] + N] = True

for i in range(1, len(X)):
    x_ = X[i]
    for j in range(2 * N):
        if j >= x_:
            if dp[i - 1][j - x_]:
                dp[i][j] = True
        if j + x_ < 2 * N:
            if dp[i - 1][j + x_]:
                dp[i][j] = True

# print (dp)
if not dp[-1][x + N]:
    print ('No')
    exit()

dp = [[False] * (2 * N) for _ in range(len(Y))]
dp[0][Y[0] + N] = True
dp[0][-Y[0] + N] = True

for i in range(1, len(Y)):
    y_ = Y[i]
    for j in range(2 * N):
        if j >= y_:
            if dp[i - 1][j - y_]:
                dp[i][j] = True
        if j + y_ < 2 * N:
            if dp[i - 1][j + y_]:
                dp[i][j] = True

if not dp[-1][y + N]:
    print ('No')
    exit()

print ('Yes')

### FIXED CODE ###

s = list(input())
x, y = map(int, input().split())

X = [0]
Y = [0]

flag = True
tmp = 0
for i in s:
    if i == 'F':
        tmp += 1
    else:
        if flag:
            X.append(tmp)
        else:
            Y.append(tmp)
        tmp = 0
        flag = not flag

if flag:
    X.append(tmp)
else:
    Y.append(tmp)

# print (X)
# print (Y)

x -= X[1]
X[1] = 0

x = abs(x)
y = abs(y)

total_X = sum(X)
total_Y = sum(Y)

lst_X = [0] * (total_X + 1)
lst_X[0] = 1
for i in X:
    if i == 0:
        continue
    for j in range(total_X - i, -1, -1):
        if lst_X[j] == 1:
            lst_X[j + i] = 1

# print (lst_X)

lst_Y = [0] * (total_Y + 1)
lst_Y[0] = 1
for i in Y:
    if i == 0:
        continue
    for j in range(total_Y - i, -1, -1):
        if lst_Y[j] == 1:
            lst_Y[j + i] = 1

# print (lst_Y)
if x > total_X or y > total_Y:
    print ('No')
    exit()

if (total_X - x) % 2 == (total_Y - y) % 2 == 0 and lst_X[(total_X - x) // 2] == 1 and lst_Y[(total_Y - y) // 2]:
    print ('Yes')
else:
    print ('No')
### BUGGY CODE ###


if __name__ == '__main__':
    n,m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    a.sort()
    for i in range(m):
        b, c = list(map(int, input().split()))
        for j in range(b):
            if(a[j] < c):
                a[j] = c
            else:
                break
        a.sort()

    print(sum(a))


### FIXED CODE ###


if __name__ == '__main__':
    n,m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    bc = []
    for i in range(m):
        bc.append(list(map(int, input().split())))

    bc.sort(key=lambda x: x[1], reverse=True)
    a.sort()

    bcn = 0
    for i in range(n):
        if(a[i] < bc[bcn][1]):
            a[i] = bc[bcn][1]
            bc[bcn][0] -= 1
            if(bc[bcn][0] == 0):
                bcn += 1
                if(bcn == m):
                    break

    print(sum(a))
### BUGGY CODE ###

def attack(x):
    if x <= 1:
        return 1
    else:
        ans = 0
        ans += attack(int(x / 2))
        ans += attack(int(x / 2))
        ans += 1
        return ans

h = int(input().rstrip())
at = attack(h)
print(at)

### FIXED CODE ###

def attack(x):
    if x <= 1:
        return 1
    else:
        ans = 0
        ans += attack(int(x / 2))
        ans *= 2
        ans += 1
        return ans

h = int(input().rstrip())
at = attack(h)

print(at)
### BUGGY CODE ###

N, M = map(int, input().split())

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

group_list = []
group_index = [0] * N

for _ in range(M):
    a, b = map(int, input().split())
    if group_index[a-1] == 0 and group_index[b-1] == 0:
        group_index[a-1] = len(group_list) + 1
        group_index[b-1] = len(group_list) + 1
        group_list.append(set([a, b]))

    elif group_index[a-1] == 0:
        group_index[a-1] = group_index[b-1]
        group_list[group_index[b-1] - 1].add(a)

    elif group_index[b-1] == 0:
        group_index[b-1] = group_index[a-1]
        group_list[group_index[a-1] - 1].add(b)

    elif group_index[a-1] != group_index[b-1]:
        group_id_b = group_index[b-1] - 1
        for p in group_list[group_id_b]:
            group_index[p-1] = group_index[a-1]
            group_list[group_index[a-1] - 1].add(p)
        group_list[group_id_b] = set()

print(max([len(g) for g in group_list]))

### FIXED CODE ###

N, M = map(int, input().split())

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

group_list = []
group_index = [0] * N

for _ in range(M):
    a, b = map(int, input().split())
    if group_index[a-1] == 0 and group_index[b-1] == 0:
        group_index[a-1] = len(group_list) + 1
        group_index[b-1] = len(group_list) + 1
        group_list.append(set([a, b]))

    elif group_index[a-1] == 0:
        group_index[a-1] = group_index[b-1]
        group_list[group_index[b-1] - 1].add(a)

    elif group_index[b-1] == 0:
        group_index[b-1] = group_index[a-1]
        group_list[group_index[a-1] - 1].add(b)

    elif group_index[a-1] != group_index[b-1]:
        if len(group_list[group_index[a-1] - 1]) > len(group_list[group_index[b-1] - 1]):
            group_id_b = group_index[b-1] - 1
            for p in group_list[group_id_b]:
                group_index[p-1] = group_index[a-1]
                group_list[group_index[a-1] - 1].add(p)
            group_list[group_id_b] = set()
        else:
            group_id_a = group_index[a-1] - 1
            for p in group_list[group_id_a]:
                group_index[p-1] = group_index[b-1]
                group_list[group_index[b-1] - 1].add(p)
            group_list[group_id_a] = set()

print(max([len(g) for g in group_list]))
### BUGGY CODE ###

n, k = map(int, input().split())
i = 0
a = list()
d = 0
while i<k:
    d += int(input())
    a += (map(int, input().split()))
    i += 1
i=0

while i<d:
    x = d-1
    while x > i:
        if a[x] < a[x-1]:
            c = a[x]
            a[x] = a[x-1]
            a[x-1] = c
        x -= 1
    i+=1

i=0
ans = a[0] - 1
while i<d-1:
    if a[i+1] - a[i]>1:
        ans += a[i+1] - a[i] -1
    i+=1
if a[d-1] != n:
    ans += n - a[d-1]

print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
i = 0
a = list()
d = 0
while i<k:
    d += int(input())
    a += (map(int, input().split()))
    i += 1
i=0

b = [0]*n
while i<d:
    b[a[i]-1]=1
    i+=1

i=0
ans = 0
while i<n:
    if b[i] ==0:
        ans += 1
    i+=1

print(ans)
### BUGGY CODE ###

s = input()

frommap = []
for d in range(10):
    frommap.append([0] * 13)
    for m in range(13):
        m2 = (m * 10 + d) % 13
        frommap[d][m2] = m

dp = [1] + [0] * 12
for c in s:
    if c == '?':
        dp = [sum(dp[frommap[d][m]] for d in range(10)) % 1000000007 for m in range(13)]
    else:
        f = frommap[int(c)]
        dp = [dp[f[m]] for m in range(13)]

print(dp[5])

### FIXED CODE ###

s = input()
dp = [1] + [0] * 12
for c in s:
    newdp = [0] * 13
    for d in range(10) if c == '?' else [int(c)]:
        for m in range(13):
            m2 = (m * 10 + d) % 13
            newdp[m2] = (newdp[m2] + dp[m]) % 1000000007
    dp = newdp
print(dp[5])
### BUGGY CODE ###

K = int(input())

queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]

for _ in range(K):
    x = queue.pop(0)
    if x % 10 != 0:
        queue.append(10 * x + x % 10 - 1)
    queue.append(10 * x + x % 10)
    if x % 10 != 9:
        queue.append(10 * x + x % 10 + 1)

print(x)

### FIXED CODE ###

from collections import deque
K = int(input())

q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

for _ in range(K):
    x = q.popleft()
    xmod = x % 10
    if xmod != 0:
        q.append(10 * x + xmod - 1)
    q.append(10 * x + xmod)
    if xmod != 9:
        q.append(10 * x + xmod + 1)
print(x)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

ex = []
for x in p:
    ex.append(1/x * (sum(list(range(1, x+1)))))

cs = [0]
for x in ex:
    cs.append(cs[-1]+x)

ans = 0
for i in range(k, n+1):
    ans = max(ans, cs[i] - cs[i-k])

print(ans)

### FIXED CODE ###

def main():

    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    ex = [0]
    for x in p:
        ex.append(ex[-1] + (x+1)/2)

    ans = 0
    for i in range(k, n+1):
        ans = max(ans, ex[i] - ex[i-k])

    print(ans)

main()
### BUGGY CODE ###

import collections
import math
n, m = [int(item) for item in input().split()]

def trial_division_sqrt(n):
    prime_count = collections.Counter()
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1
 
    return prime_count

cnt = trial_division_sqrt(m)

ans = 1
for item in cnt:
  ans *= int(math.factorial(n + cnt[item] - 1) // int(math.factorial(cnt[item]) * math.factorial(n-1)))
  ans = int(ans) % (1000000000 + 7)
print(ans)

### FIXED CODE ###

import collections
import math
n, m = [int(item) for item in input().split()]

def trial_division_sqrt(n):
    prime_count = collections.Counter()
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1
    return prime_count

cnt = trial_division_sqrt(m)

ans = 1
for item in cnt:
  h = 1
  k_fact = 1
  for i in range(cnt[item]):
    h *= n + cnt[item] - 1 - i
    k_fact *= (i+1)
  ans *= h
  ans = ans // k_fact
  ans = ans % (1000000000 + 7)
print(ans)
### BUGGY CODE ###

count = 0
n = int(input())
lst = map(int, input().split())
while all([i%2 == 0 for i in lst]):
  lst = [i // 2 for i in lst]
  count += 1
print(count)

### FIXED CODE ###

n = int(input())
a = map(int, input().split())
m = float('inf')
for i in a:
  count = 0
  while i%2 == 0:
    i = i//2
    count += 1
  m = min(m, count)
  if m==0:
    break
print(m)
### BUGGY CODE ###

A, B = map(int, input().split())
l = []
for i in range(1, A * B + 1):
    if i % A == 0 and i % B == 0:
        l.append(i)
print(min(l))

### FIXED CODE ###

A, B = map(int, input().split())
num = 0
for i in range(B + 1):
    num += A
    if  num % B == 0:
        break
print(num)
### BUGGY CODE ###

# cook your dish here
n=int(input())
if n%4==0:
    print("Yes")
elif n%7==0:
    print("Yes")
else:
    p=1
    t=True
    while p<100:
        if (n-(4*p))%7 ==0:
            t=False
            print("Yes")
            break
    if t:
        print("No")

### FIXED CODE ###

n=int(input())
p=0
t=True
while p<26:
    r=n-(7*p)
    if r>=0 and r%4 ==0:
        t=False
        print("Yes")
        break
    p+=1
if t:
    print("No")
### BUGGY CODE ###

import random


class Dice(object):
    def __init__(self):
        self.t = 1
        self.s = 2
        self.e = 3
        self.w = 4
        self.n = 5
        self.b = 6

    def __init__(self, faces):
        self.t = faces[0]
        self.s = faces[1]
        self.e = faces[2]
        self.w = faces[3]
        self.n = faces[4]
        self.b = faces[5]

    def roll(self, direct):
        if direct == 0:
            self.t, self.s, self.b, self.n = self.n, self.t, self.s, self.b
        elif direct == 1:
            self.t, self.w, self.b, self.e = self.e, self.t, self.w, self.b
        elif direct == 2:
            self.n, self.w, self.s, self.e = self.w, self.s, self.e, self.n

    def is_equal(self, dice):
        if self.t == dice.t and self.s == dice.s and self.e == dice.e and self.w == dice.w and self.n == dice.n and self.b == dice.b:
            return True
        else:
            return False

n = int(input())
dice_list = []
flag_list = []
for _ in range(n):
    flag = False
    faces = list(map(int, input().split()))
    dice_list.append(Dice(faces))

    if n == 0:
        continue

    dice_a = dice_list[-1]
    for i in range(len(dice_list) - 1):
        dice_b = dice_list[i]

        for i in range(10000):
            dice_b.roll(random.randint(0, 3))
            if dice_a.is_equal(dice_b):
                flag = True
                break

        flag_list.append(flag)

if any(flag_list):
    print('No')
else:
    print('Yes')



### FIXED CODE ###

import random


class Dice(object):
    def __init__(self):
        self.t = 1
        self.s = 2
        self.e = 3
        self.w = 4
        self.n = 5
        self.b = 6

    def __init__(self, faces):
        self.t = faces[0]
        self.s = faces[1]
        self.e = faces[2]
        self.w = faces[3]
        self.n = faces[4]
        self.b = faces[5]

    def roll(self, direct):
        if direct == 0:
            self.t, self.s, self.b, self.n = self.n, self.t, self.s, self.b
        elif direct == 1:
            self.t, self.w, self.b, self.e = self.e, self.t, self.w, self.b
        elif direct == 2:
            self.n, self.w, self.s, self.e = self.w, self.s, self.e, self.n

    def is_equal(self, dice):
        if self.t == dice.t and self.s == dice.s and self.e == dice.e and self.w == dice.w and self.n == dice.n and self.b == dice.b:
            return True
        else:
            return False

    def get_nums(self):
        return {self.t, self.s, self.e, self.w, self.n, self.b}

n = int(input())
dice_list = []
flag_list = []
for _ in range(n):
    flag = False
    faces = list(map(int, input().split()))
    dice_list.append(Dice(faces))

    if n == 0:
        continue

    dice_a = dice_list[-1]
    for i in range(len(dice_list) - 1):
        dice_b = dice_list[i]

        if (dice_a.get_nums() == dice_b.get_nums()):
            for i in range(1000):
                dice_b.roll(random.randint(0, 3))
                if dice_a.is_equal(dice_b):
                    flag = True
                    break

        flag_list.append(flag)

if any(flag_list):
    print('No')
else:
    print('Yes')
### BUGGY CODE ###

n,q=map(int,input().split())
a=[0]*(n-1)
c=[0 for i in range(n)]
for i in range(n-1):
  a[i]=list(map(int,input().split()))
 
a.sort()
 
for i in range(q):
  x,y=map(int,input().split())
  c[x-1]+=y
 
for i in range(n-1):
  c[a[i][1]-1]+=c[a[i][0]-1]
 
print(*c)

### FIXED CODE ###

n,q=map(int,input().split())
a=[0]*(n-1)
c=[0 for i in range(n)]
for i in range(n-1):
  a[i]=list(map(int,input().split()))

a.sort()

for i in range(q):
  x,y=map(int,input().split())
  c[x-1]+=y

for i in range(n-1):
  c[a[i][1]-1]+=c[a[i][0]-1]

print(*c)
### BUGGY CODE ###

a,b,x =map(int,input().split())
ans =0
for i in range(a,b+1):
  if i % x ==0: ans +=1
print(ans)

### FIXED CODE ###

a,b,x =map(int,input().split())
print((b//x)-((a-1)//x))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000000001)
ab = abs; mn = min

def solve(n,k,ar,dp,x):
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	m = 1e9
	for i in range(x+1,mn(n,x+k+1)):
		m = mn(m,ab(ar[x]-ar[i])+solve(n,k,ar,dp,i))
	dp[x] = m
	# pr(f'{x} => {dp[x]}')
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [ab(ar[-2]-ar[-1]),0]
	# pr((n,k,ar,dp))
	pr(solve(n,k,ar,dp,0))

main()

### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
### BUGGY CODE ###

power = 1
for i in range(int(input())):
	power *= i+1
print(power % (10**9+7))

### FIXED CODE ###

power=1
for i in range(int(input())):
  power = (i+1)*power%(10**9+7)
print(power)
### BUGGY CODE ###

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

a_list = [int(x) for x in input().split()]
a_list.sort()

mod = 10 ** 9 + 7

temp_list = [1] * (n + 1)
for i in range(1, n + 1):
    temp_list[i] = i * temp_list[i - 1] % mod

i_temp_list = [1] * (n + 1)
i_temp_list[-1] = pow(temp_list[-1], mod - 2, mod)
for i in range(n, 0, -1):
    i_temp_list[i - 1] = i_temp_list[i] * i % mod

y = k - 2

ans = 0
for i in range(n - k + 1):
    for j in range(i + k - 1, n):
        f = a_list[j] - a_list[i]

        x = j - i - 1
        num = temp_list[x] * i_temp_list[y] * i_temp_list[x - y] % mod

        ans += f * num % mod

ans %= mod
print(ans)

### FIXED CODE ###

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

a_list = [int(x) for x in input().split()]
a_list.sort()

mod = 10 ** 9 + 7

temp_list = [1] * (n + 1)
for i in range(1, n + 1):
    temp_list[i] = i * temp_list[i - 1] % mod

i_temp_list = [1] * (n + 1)
i_temp_list[-1] = pow(temp_list[-1], mod - 2, mod)
for i in range(n, 0, -1):
    i_temp_list[i - 1] = i_temp_list[i] * i % mod

y = k - 1

ans = 0
for i in range(k - 1, n):
        x = i
        num = temp_list[x] * i_temp_list[y] * i_temp_list[x - y] % mod
        ans += a_list[i] * num % mod
for i in range(n - k + 1):
        x = n - 1 - i
        num = temp_list[x] * i_temp_list[y] * i_temp_list[x - y] % mod
        ans -= a_list[i] * num % mod

ans %= mod
print(ans)
### BUGGY CODE ###

import itertools

N = int(input())
S = input()

ans = 0
num_list = [i for i in range(N)]
for v in itertools.combinations(num_list, 3):
    left_num = v[0]
    mid_num = v[1]
    right_num = v[2]
    if abs(left_num - mid_num) != abs(mid_num - right_num):
        if S[left_num] != S[mid_num] and S[mid_num] != S[right_num] and S[left_num] != S[right_num]:
            ans += 1
            
print(ans)


### FIXED CODE ###

N = int(input())
S = input()

R = []
G = []
B = []
for i in range(N):
    if S[i] == "R":
        R.append(i)
    elif S[i] == "G":
        G.append(i)
    else:
        B.append(i)
        
ans = len(R) * len(G) * len(B)
for i in R:
    for j in G:
        if abs(j-i) % 2 == 1:
            k1 = min(j, i) - abs(j-i)
            k2 = max(j, i) + abs(j-i)
            if k1 >= 0:
                if S[k1] == "B":
                    ans -= 1
            if k2 <= N-1:
                if S[k2] == "B":
                    ans -= 1
        else:
            k1 = min(j, i) - abs(j-i)
            k2 = max(j, i) + abs(j-i)
            k3 = min(j, i) + abs(j-i)//2
            if k1 >= 0:
                if S[k1] == "B":
                    ans -= 1
            if k2 <= N-1:
                if S[k2] == "B":
                    ans -= 1
            if S[k3] == "B":
                ans -= 1
            
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


n=int(input())
A=list(map(int,input().split()))
v=[-1]*n
for i,a in enumerate(A):
    #print(i,a)
    if v[a-1]!=-1:
        s=v[a-1]
        f=i
    if v[a-1]==-1:
        v[a-1]=i

#print(s,f)
mod=10**9+7
for i in range(1,n+1):
    """sousuu=cmb(n+1,i,mod)
    tyouhuku=cmb(s+n-f,i-1,mod)"""
    if i==1:
        sousuu=n+1
        tyouhuku=1
    else:
        sousuu*=(n+2-i)
        sousuu//=i
        tyouhuku*=(s+n-f+1-i+1)
        tyouhuku//=(i-1)
    #print(sousuu,tyouhuku)
    print((sousuu-tyouhuku)%mod)
print(1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
########   modあり modは素数  ###############
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


n=int(input())
A=list(map(int,input().split()))
v=[-1]*n
for i,a in enumerate(A):
    #print(i,a)
    if v[a-1]!=-1:
        s=v[a-1]
        f=i
    if v[a-1]==-1:
        v[a-1]=i

#print(s,f)
mod=10**9+7
for i in range(1,n+1):
    sousuu=cmb(n+1,i,mod)
    tyouhuku=cmb(s+n-f,i-1,mod)
    """if i==1:
        sousuu=n+1
        tyouhuku=1
    else:
        sousuu*=(n+2-i)
        sousuu//=i
        tyouhuku*=(s+n-f+1-i+1)
        tyouhuku//=(i-1)"""
    #print(sousuu,tyouhuku)
    print((sousuu-tyouhuku)%mod)
print(1)
### BUGGY CODE ###

from collections import deque

def bfs(neighbor,start):
    order = [0 for i in range(N)]
    visited = [0 for i in range(N)]
    visited[start] = 1
    q = deque([start])
    num = 1
    while q:
        path = q.popleft()
        order[path] = num
        visited[path] = 1
        num += 1
        for v in neighbor[path]:
            if visited[v] == 1:
                continue
            q.append(v)
    order = [[i,order[i]] for i in range(len(neighbor))]
    order.sort(key=lambda x:x[1])
    return [order[i][0] for i in range(len(order))]


N = int(input())
node = [[0,i] for i in range(N)]
ab = []
neigh = [[0 for i in range(N)] for j in range(N)]
for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1][0] += 1
    node[bi-1][0] += 1
    neigh[ai-1][bi-1] = 1
    neigh[bi-1][ai-1] = 1
    ab.append([ai-1,bi-1])
c = list(map(int,input().split()))
c.sort(reverse=True)
node.sort(key=lambda x:x[0],reverse=True)
m = max([node[i][0] for i in range(N)])
max_node = [node[i][1] for i in range(N) if node[i][0] == m]
ans1 = 0
for nn in max_node:
    can = 0
    bbb = bfs(neigh,nn)
    cn = [[c[i],bbb[i]] for i in range(N)]
    #cn.sort(key=lambda x:x[1])
    for i in range(N-1):
        can += min(cn[ab[i][0]][0],cn[ab[i][1]][0])
    if can > ans1:
        ans1 = can
        ans2 = ' '.join([str(cn[i][0]) for i in range(N)])

        
print(ans1)

print(ans2)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            try:
                dfs(neighbor,i)
            except RuntimeError:
                flag = True
                return 0




m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)

dfs(neigh,nn)
"""
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)
### BUGGY CODE ###

S = input()
T = input()
len_s = len(S)
ok = True
for i in range(len_s):
  for j in range(i+1, len_s):
    if (S[i] == S[j] and T[i] != T[j]) or (S[i] != S[j] and T[i] == T[j]):
      ok = False
      break
if ok:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

S = input()
T = input()
len_s = len(S)
ok = True
s_dict = {}
t_dict = {}
for i in range(len_s):
  if S[i] in s_dict and s_dict[S[i]] != T[i]:
    ok = False
    break
  if T[i] in t_dict and t_dict[T[i]] != S[i]:
    ok = False
    break
  s_dict[S[i]] = T[i]
  t_dict[T[i]] = S[i]
if ok:
  print('Yes')
else:
  print('No')