Harryxun/stf_run huggingface dataset:
def count_section_by_zero(data):
  count = 0
  flg = False
  start = 0
  for i, d in enumerate(data):
    if flg is False and d != 0:
      count += 1
      flg = True
      
    if d == 0:
      flg = False
  return count

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

def input_list_str():
  return list(map(str, input().split()))

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
  n,k = input_list()
  p = input_list()
  kakus = [1+p[0]/2]
  for i in range(1, n):
    kaku = (1+p[i])/2
    pre = kakus[i-1]
    kakus.append(kaku+pre)
  ans = []
  for i in range(len(p)-k):
    ans.append(kakus[i+k]-kakus[i])
  print(max(ans))
  
import math
import fractions
import collections
import itertools
from functools import reduce
main()

### FIXED CODE ###

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

def kitai(x):
  return (1+int(x))/2

p = list(map(kitai, input().split()))

pre = psum = sum(p[0:k])

for i in range(1, n):
  if i+k > n:
    break
  pre = pre - p[i-1] + p[i+k-1]
  psum = max(psum, pre)

print(psum)
while True:
    (n, x) = [int(i) for i in input().split()]
    if n == x ==0
        break

### FIXED CODE ###

while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break
  
    result = 0
    for a in range(1, x // 3):
        for b in range(a + 1,  x // 2):
            c = x - a - b
            if b < c <= n:
                result += 1    
    print(result)
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("void(i8,i8,i8,i8[:,:],i8[:,:])", cache=True)
def dfs(H, W, D, A, mp):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i][i + D] = abs(x - w) + abs(y - h)

    for i in range(1, H * W + 1 - 2 * D):
        for j in range(i + 2 * D, H * W + 1):
            mp[i][j] = mp[i][j - D] + mp[j - D][j]


def main():
    H, W, D = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=np.int64)
    for i in range(H):
        A[i] = list(map(int, input().split()))
    Q = int(input())
    L = [0] * Q
    R = [0] * Q
    for i in range(Q):
        L[i], R[i] = map(int, input().split())

    mp = np.zeros(shape=(H * W + 1, H * W + 1), dtype=np.int64)
    dfs(H, W, D, A, mp)

    ans = [mp[l, r] for l, r in zip(L, R)]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("void(i8,i8,i8,i8[:,:],i8,i8[:,:],i8[:])", cache=True)
def dfs(H, W, D, A, Q, LR, ans):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

    mp = np.zeros(shape=(H * W + 1), dtype=np.int64)

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i + D] = abs(x - w) + abs(y - h)

    for d in range(1, D + 1):
        mp[d::D] = np.cumsum(mp[d::D])

    for i in range(Q):
        l, r = LR[i]
        ans[i] = mp[r] - mp[l]


def main():
    H, W, D = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=np.int64)
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = np.zeros(shape=(Q, 2), dtype=np.int64)
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = np.zeros(shape=Q, dtype=np.int64)
    dfs(H, W, D, A, Q, LR, ans)

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]
n = [0] * N
n[0] = 1
n[1] = 2

if 1 in a and N == 1: print(0), exit()

for i in range(N - 2):
    if i + 3 not in a:
        n[i + 2] = n[i + 1] + n[i]
print(n[N - 1])

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for i in range(M)])
n = [0] * (N + 1)
n[0] = 1
n[1] = 1

#listの中をinで探すのはくっそ遅い
if 1 in a:
    n[1] = 0

for i in range(2, N + 1):
    if i in a:
        continue
    else:
        n[i] = (n[i - 1] + n[i - 2]) % 1000000007

print(n[N])
#a,b=map(int,input().split())
a=input()
if(a<2800):
	print("ABC")
else:
	print("ARC")


### FIXED CODE ###

a=int(input())
if a<1200:
	print("ABC")
elif a<2800:
	print("ARC")
else:
	print("AGC")
from math import ceil
A, B = map(int, input())
print(ceil(B/A))

### FIXED CODE ###

from math import ceil
A, B = map(int, input().split())
if B == 1:
    print(0)
else:
    print(int(ceil((B-1)/(A-1))))
n=int(input())
build,story,room,people=[],[],[],[]
for i in range(n):
    date=list(map(int,input().split(' ')))
    build.append(date[0])
    story.append(date[1])
    room.append(date[2])
    people.append(date[3])
build1=[[0 for i in range(10)] for j in range(3)]
build2=[[0 for i in range(10)] for j in range(3)]
build3=[[0 for i in range(10)] for j in range(3)]
build4=[[0 for i in range(10)] for j in range(3)]

for i in range(n):
    m=int(i)
    if(build[m]==1):
        build1[story[m]-1][room[m]-1]=build1[story[m]-1][room[m]-1]+people[m]
    if(build[m]==2):
        build2[story[m]-1][room[m]-1]=build1[story[m]-1][room[m]-1]+people[m]
    if(build[m]==3):
        build3[story[m]-1][room[m]-1]=build1[story[m]-1][room[m]-1]+people[m]
    if(build[m]==4):
        build4[story[m]-1][room[m]-1]=build1[story[m]-1][room[m]-1]+people[m]

for i in range(3):
    print(' '+' '.join(list(map( lambda x: str(x),build1[i]))))
print('#'*20)
for i in range(3):
    print(' '+' '.join(list(map( lambda x: str(x),build2[i]))) )
print('#'*20)
for i in range(3):
    print(' '+' '.join(list(map( lambda x: str(x),build3[i]))) )
print('#'*20)
for i in range(3):
    print(' '+' '.join(list(map( lambda x: str(x),build4[i]))) )


### FIXED CODE ###

n=int(input())
build,story,room,people=[],[],[],[]
for i in range(n):
    date=list(map(int,input().split(' ')))
    build.append(date[0])
    story.append(date[1])
    room.append(date[2])
    people.append(date[3])
build1=[[0 for i in range(10)] for j in range(3)]
build2=[[0 for i in range(10)] for j in range(3)]
build3=[[0 for i in range(10)] for j in range(3)]
build4=[[0 for i in range(10)] for j in range(3)]
for i in range(n):
    m=int(i)
    if(build[m]==1):
        build1[story[m]-1][room[m]-1]=build1[story[m]-1][room[m]-1]+people[m]
    elif(build[m]==2):
        build2[story[m]-1][room[m]-1]=build2[story[m]-1][room[m]-1]+people[m]
    elif(build[m]==3):
        build3[story[m]-1][room[m]-1]=build3[story[m]-1][room[m]-1]+people[m]
    else:
        build4[story[m]-1][room[m]-1]=build4[story[m]-1][room[m]-1]+people[m]

for i in range(3):
    print(' '+' '.join(list(map( lambda x: str(x),build1[i]))))
print('#'*20)
for i in range(3):
    print(' '+' '.join(list(map( lambda x: str(x),build2[i]))) )
print('#'*20)
for i in range(3):
    print(' '+' '.join(list(map( lambda x: str(x),build3[i]))) )
print('#'*20)
for i in range(3):
    print(' '+' '.join(list(map( lambda x: str(x),build4[i]))) )
N, M = map(int, input().split())
A = map(int, input().split())

ans1 = sum(A)
ans2 = N - ans1

if sns2 < 0:
    print(-1)
else:
    print(ans2)

### FIXED CODE ###


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

ans = N - sum(A)

if ans < 0:
    print(-1)
else:
    print(ans)
n,m = map(int,input().split())
a = [0] * m
for i in range(m):
    a[i] = int(input())

dp = [0] * (n + 1)
if 0 not in a:
    dp[0] = 1
if 1 not in a:
    dp[1] = 1
if 2 not in a:
    if 1 in a:
        dp[2] = 1
    else:
        dp[2] = 2

mod = 10**9+7

for i in range(3,n+1):
    if i-1 in a and i-2 in a:
        dp[i] = 0
    elif i-1 in a:
        dp[i] = dp[i-2] % mod
    elif i-2 in a:
        dp[i] = dp[i-1] % mod
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[-1])


### FIXED CODE ###

n,m = map(int,input().split())
a = [0] * m
for i in range(m):
    a[i] = int(input())

dp = [999] * (n + 1)
if 0 not in a:
    dp[0] = 1
if 1 not in a:
    dp[1] = 1
if 2 not in a and n >= 2:
    if 1 in a:
        dp[2] = 1
    else:
        dp[2] = 2

mod = 10**9+7

for i in range(len(a)):
    dp[a[i]] = 0

for i in range(3,n+1):
    if dp[i] != 0:
        dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[-1])
s = input()
t = input()

count = 0

for i in ronge(len(s)):
  if s[i] != t[i]:
    count = count + 1
    
print(count)

### FIXED CODE ###

s = input()
t = input()
 
count = 0
 
for i in range(len(s)):
  if s[i] != t[i]:
    count = count + 1
    
print(count)
a,s = input().split() 
if int(a) >= 3200:
    print(s)
else:
    print('red')

### FIXED CODE ###

a,s = [input() for i in range(2)]
if int(a) >= 3200:
    print(s)
else:
    print('red')
S = list( input() )
new = [ S[1]-S[0], S[2]-S[1], S[3]-S[2] ]
if 0 in new : 
   print( "Good" )
else : 
   print( "Bad" )

### FIXED CODE ###

S = list( input() )
for i in range( len(S) - 1 ) : 
    if S[i] == S[i+1] : 
       print( "Bad" )
       break
else : 
    print( "Good" )
import collections

def answer(list,n):
    Even = collections.Counter(list[::2]).most_common(2)
    Odd = collections.Counter(list[1::2]).most_common(2)

    if Even[0][0] != Odd[0][0]:
        return n - Even[0][1] - Odd[0][1]
    else:
        if len(Even) == 1 or len(Odd) == 1:
            return n // 2
        else:
            return n - max(Even[0][1]+Odd[1][1],Even[1][1]+Odd[0][1])

N = int(input())
list = input().split(" ")
print(answer(list,N))


### FIXED CODE ###

ans = int(input())
print(1110-ans)
n,k=map(int,input().split())
if n>k:
    val=n-k
    print(n%val)
else:
    val=k-n
    print(k%val)


### FIXED CODE ###

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

if k==1:
    print(0)
elif n>k:
    print(k-(n%k))
else:
    val=k-n
    if n<val:
        print(n)
    else:
        print(val)
a,b = int(input())
if a>b:
	print("Alice")
elif a<b:
	print("Bob")
else:
	print("Draw")

### FIXED CODE ###

a,b = map(int,input().split())
if a==1:
	a=14
if b==1:
	b=14
if a>b:
	print("Alice")
elif a<b:
	print("Bob")
else:
	print("Draw")
n,m,c=map(int,input().split())
B=list(map(int,input().split()))
A=[list(map(int, input().split()))for i in range(n)]
cnt = 0
for i in range(n):
  total = 0
  for j in range(m):
    total += b[j] * a[i][j]
  total += c
  if total > 0:
    cnt += 1
print(cnt)

### FIXED CODE ###

n,m,c=map(int,input().split())
B=list(map(int,input().split()))
A=[list(map(int, input().split()))for i in range(n)]
cnt = 0
for i in range(n):
  total = 0
  for j in range(m):
    total += B[j] * A[i][j]
  total += c
  if total > 0:
    cnt += 1
print(cnt)
import collections

n=int(input())
lst=[]
ans=0

for i in range(n):
  s=input()
  s.sort()
  lst+=[s]
  
  c=collections.Counter(s)
  
for i in c.values():
  ans+=i*(i-1)//2
  
print(ans)

### FIXED CODE ###

import collections

n=int(input())
lst=[]
ans=0

for i in range(n):
    s=input()
    lst.append(''.join(sorted(s)))

c=collections.Counter(lst)

for i in set(lst):
    x=c[i]

    ans+=x*(x-1)//2


print(ans)
import sys

def main():
    a = int(sys.argv[1])
    b = int(sys.argv[2])
    c = int(sys.argv[3])
    result = c-(a-b)
    if result < 0:
        result = 0

    print(result)
    sys.exit(2)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    a, b, c = map(int, input().split())
    result = c-(a-b)
    if result < 0:
        result = 0

    print(result)

if __name__ == "__main__":
    main()
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        f1 = True
        f2 = True
        f3 = True
        f4 = True
        for i in range(1,k+1):
            if f1 and cord[y][x+i] == '.':
                l.append((x+i,y))
            elif cord[y][x+i] == '@':
                f1 = False
            if f2 and cord[y][x-i] == '.':
                l.append((x-i,y))
            elif cord[y][x-i] == '@':
                f2 = False
            if f3 and cord[y+i][x] == '.':
                l.append((x,y+i))
            elif cord[y+i][x] == '@':
                f3 = False
            if f4 and cord[y-i][x] == '.':
                l.append((x,y-i))
            elif cord[y-i][x] == '@':
                f4 = False
            if not (f1 or f2 or f3 or f4):
                break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = '#'
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '#'
#for i in cord:
#    print(*i)
print(bfs(xg,yg))

### FIXED CODE ###

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        f1 = True
        f2 = True
        f3 = True
        f4 = True
        for i in range(1,k+1):
            if f1:
                if cord[y][x+i] == '.':
                    l.append((x+i,y))
                elif cord[y][x+i] == '@' or cord[y][x+i] != dep+1:
                    f1 = False
            if f2:
                if cord[y][x-i] == '.':
                    l.append((x-i,y))
                elif cord[y][x-i] == '@' or cord[y][x-i] != dep+1:
                    f2 = False
            if f3:
                if cord[y+i][x] == '.':
                    l.append((x,y+i))
                elif cord[y+i][x] == '@' or cord[y+i][x] != dep+1:
                    f3 = False
            if f4:
                if cord[y-i][x] == '.':
                    l.append((x,y-i))
                elif cord[y-i][x] == '@' or cord[y-i][x] != dep+1:
                    f4 = False
            if not (f1 or f2 or f3 or f4):
                break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = dep+1
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '#'
#for i in cord:
#    print(*i)
#print(len(cord),len(cord[0]))

print(bfs(xg,yg))
N = int(input())
S = list(input())
i_set = list()

ans_list = {}


for i in range(N):
    if i in i_set:
        continue
    i_set.append(i)
    for j in range(i+1, N):
        if not S[j + 1:N] or S[i] + S[j] in S_set:
            continue
        ans_list[S[i] + S[j]] = S[j + 1:N]
        S_set.add(S[i] + S[j])
count = 0
# print(ans_list)
ans_len_list = [len(set(value)) for value in ans_list.values()]
print(sum(ans_len_list))

### FIXED CODE ###

N = int(input())
S = list(input())
visited = {}

count = 0

for i, s in enumerate(S):
    if s in visited:
        continue
    visited[s] = []
    for j, s2 in enumerate(S[i+1:N-1]):
        # print(s, s2, S[i + j + 2:N])
        if s2 in visited[s]:
            continue
        count += len(set(S[i + j + 2:N]))
        visited[s].append(s2)
        # print(s, s2, set(S[j + 1:N]))
print(count)
n,k=map(int,input().split())
p=list(map(int,input().split()))
p.sort()
_sum=0
for i in range(k):
  _sum += p[k]
print(_sum)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
p.sort()
_sum=0
for i in range(k):
    _sum += p[i]
print(_sum)
from collections import deque
import sys
sys.setrecursionlimit(10000000000)

def main():
    process_count, process_time, processes = get_input()
    result =  run_roundrobin(processes = processes, time = process_time)
    for r in result:
        print(r.name, r.time)


def run_roundrobin(processes, time, total_time = 0, result=[]):
    if not processes:
        return result

    p = processes.popleft()
    if p.time <= time:
        total_time += p.time
        p.time = total_time
        result.append(p)
    else:
        total_time += time
        p.time -= time
        processes.append(p)

    return run_roundrobin(processes, time, total_time, result)



def get_input():
    count, time = list(map(lambda x: int(x), input().split(' ')))

    processes = deque([])
    for _ in range(count):
        im = input().split(' ')
        p = Process(im[0], int(im[1]))
        processes.append(p)

    return count, time, processes


class Process():

    def __init__(self, name, time):
        self.name = name
        self.time = time


main()

### FIXED CODE ###

from collections import deque


def main():
    process_count, process_time, processes = get_input()
    result = run_roundrobin(processes=processes, time=process_time)
    for r in result:
        print(r.name, r.time)


def run_roundrobin(processes, time, total_time=0, result=[]):
    while processes:
        p = processes.popleft()
        if p.time <= time:
            total_time += p.time
            p.time = total_time
            result.append(p)
        else:
            total_time += time
            p.time -= time
            processes.append(p)

    return result


def get_input():
    count, time = list(map(lambda x: int(x), input().split(' ')))

    processes = deque([])
    for _ in range(count):
        im = input().split(' ')
        p = Process(im[0], int(im[1]))
        processes.append(p)

    return count, time, processes


class Process():

    def __init__(self, name, time):
        self.name = name
        self.time = time


main()
n = input().split()
n = [int(i) for i in n]
m = input().split()
m = [int(i) for i in m]
 
ans_1 = n[0]
ans_2 = n[0]
 
ans = []
while True:
  	if n[1] == 0:
      ans.append(0)
      
    ans_1 += 1
    ans_2 -= 1
    if not ans_1 in m:
        ans.append(ans_1)
        
    elif not ans_2 in m:
        ans.append(ans_2)
    
    if len(ans) > 0:
        break
        
print(min(ans))

### FIXED CODE ###

n = input().split()
n = [int(i) for i in n]
if not n[1] == 0:
	m = input().split()
	m = [int(i) for i in m]
else:
  	m =[0]

ans_1 = n[0]
ans_2 = n[0]
ans = []
while True:
    if n[1] == 0:
        ans.append(n[0])
    if not n[0] in m:
      ans.append(n[0])
    if len(ans) > 0:
        break    
        
    ans_1 += 1
    ans_2 -= 1
    if not ans_1 in m:
        ans.append(ans_1)
    if not ans_2 in m:
        ans.append(ans_2)
    
    
        
print(min(ans))
i=R*3.1415*2
print(i)

### FIXED CODE ###

R=int(input())
i=R*6.283184
print(i)
def f(i,k):
  for j in range(13):
    dp[i+1][(j*10+k)%13]+=dp[i][j]
    dp[i+1][(j*10+k)%13]%=mod
  
mod=10**9+7
s=input()
n=len(s)
dp=[[0]*13 for i in range(10**5)]
dp[0][0]=mul=1

for i in range(n):
  if s[i]=='?':
    for k in range(10):
      f(i,k)
  else:
    f(i,int(s[i]))
  
print(dp[n][5]%mod)


### FIXED CODE ###

def f(i,k):
  for j in range(13):
    dp[i+1][(j*10+k)%13]+=dp[i][j]
    dp[i+1][(j*10+k)%13]%=mod
  
mod=10**9+7
s=input()
n=len(s)
dp=[[0]*13 for i in range(10**5+1)]
dp[0][0]=mul=1

for i in range(n):
  if s[i]=='?':
    for k in range(10):
      f(i,k)
  else:
    f(i,int(s[i]))
  
print(dp[n][5]%mod)
n=int(input())
t=[int(input()) for _ in range(n)]

import fractions
a,b=t[0],t[1]
res=a*b//fractions.gcd(a,b)
for i in range(2,n-1):
    a,b=t[i],t[i+1]
    res = a*b//fractions.gcd(a,b)
print(res)

### FIXED CODE ###

n=int(input())
t=[int(input()) for _ in range(n)]

import fractions
if n==1: print(t[0])
else:
    a,b=t[0],t[1]
    res=a*b//fractions.gcd(a,b)
    for i in range(2,n):
        tmp=t[i]
        res = res*tmp//fractions.gcd(res,tmp)
    print(res)
n = int(input())
t = list(map(int, input().strip().split()))

r = 1
for tt in t:
    r *= tt

rr = r - 10**18
if rr > 0:
    print(-1)
else:
    print(r)

### FIXED CODE ###

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

print(a * b)
while True:
    T,D,L = map(int,input().split())
    if T==0 and D ==0 and L == 0:
        break
    x = [int(input()) for i in range(T)]
    l = [0]*(T-1)
    i = 0
    m = 0
    while i<T-1:
         #for i in range(T-1):
        if m < i:
            m = i
        if x[i] >= L and D > m-i:
            tmp=m
            for j in range(D-(tmp-i)):
                if tmp<T-1:
                    l[tmp+j] = 1
                    m += 1
        i+=1
    total = 0
    for i in range(T-1):
        total += l[i]

    print(total)


### FIXED CODE ###

while True:
    T,D,L = map(int,input().split())
    if T==0 and D ==0 and L == 0:
        break
    x = [int(input()) for i in range(T)]
    beforeflag=0
    flag=0
    total=0
    for i in range(T):
        if x[i]>=L:
            flag=1
            if beforeflag!=D+1 and beforeflag!=0:
                total+=1
        elif x[i]<L and flag>0 and flag<=D:
            flag+=1
            total+=1
        else:
            flag=0
        beforeflag=flag
    print(total)
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
c = list(map(int,input().split()))
c.sort()
ans = sum(c) - max(c)
F = []
for i in range(1,N+1):
    n = len(G[i])
    if n == 1:
        F.append(i)
d = {}
i = 0
while len(F) != 0:
    x = F.pop(0)
    d[x] = c[i]
    i += 1
    if len(G[x]) > 0:
        y = G[x][0]
        G[y].remove(x)
        if y not in F:
            F.append(y)
ANS = []
for i in range(1,N+1):
    ANS.append(d[i])
print(ans)
print(*ANS)

### FIXED CODE ###

N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
c = list(map(int,input().split()))
c.sort()
ans = sum(c) - max(c)
F = []
for i in range(1,N+1):
    n = len(G[i])
    if n == 1:
        F.append(i)
d = {}
i = 0
while i < N:
    x = F.pop(0)
    d[x] = c[i]
    i += 1
    if len(G[x]) > 0:
        y = G[x][0]
        G[y].remove(x)
        if len(G[y]) == 1:
            F.append(y)
ANS = []
for i in range(1,N+1):
    ANS.append(d[i])
print(ans)
print(*ANS)
import sys
import math
from bisect import bisect_left
def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
def bs(a,n,x): 
    i = bisect_left(a, x) 
    if i<n and a[i] == x:
    	return i
    elif i:
    	return (i-1) 
    else: 
        return -1
n,m,k = MI()
a = LI()
b = LI()
for i in range(1,n):
	a[i]+=a[i-1]
for i in range(1,m):
	b[i]+=b[i-1]
ans = max(bs(a,n,k),bs(b,m,k))+1
for i in range(n):
	if k<a[i]:
		break
	else:
		temp = i+1+bs(b,m,k-a[i])+1
		ans = max(ans,temp)
for j in range(m):
	if k<b[i]:
		break
	else:
		temp = i+1+bs(a,n,k-b[i])+1
print(ans)



### FIXED CODE ###

import sys
import math
from bisect import bisect_left
def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
def bs(a,n,x): 
    i = bisect_left(a, x) 
    if i<n and a[i] == x:
    	return i
    elif i:
    	return (i-1) 
    else: 
        return -1
n,m,k = MI()
a = LI()
b = LI()
for i in range(1,n):
	a[i]+=a[i-1]
for i in range(1,m):
	b[i]+=b[i-1]
ans = max(bs(a,n,k),bs(b,m,k))+1
for i in range(n):
	if k<a[i]:
		break
	else:
		temp = i+1+bs(b,m,k-a[i])+1
		ans = max(ans,temp)
for i in range(m):
	if k<b[i]:
		break
	else:
		temp = i+1+bs(a,n,k-b[i])+1
		ans = max(ans,temp)
print(ans)