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

def main():
    n, t = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(n)]
    dp = [0 for i in range(t)]
    ls = [[] for i in range(t)]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[i][0] >= 0 and dp[j - f[i][0]] + f[i][1] > dp[j]:
                dp[j] = dp[j - f[i][0]] + f[i][1]
                ls[j] = ls[j - f[i][0]] + [i]
    res = dp[t - 1]
    ff = [f[i][1] for i in range(n) if not i in ls[t - 1]]
    if ff:
        return res + max(ff)
    else:
        return res


print(main())


### FIXED CODE ###



def main():
    n, t = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(n)]
    dp1 = [[0 for i in range(t)]for j in range(n+1)]
    dp2 = [[0 for i in range(t)]for j in range(n+1)]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[i][0] >= 0:
                dp1[i+1][j] = max(dp1[i][j - f[i][0]] + f[i][1],dp1[i][j])
            else:
                dp1[i+1][j] = dp1[i][j]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[n-1-i][0] >= 0:
                dp2[i+1][j] = max(dp2[i][j - f[n-1-i][0]] + f[n-1-i][1],dp2[i][j])
            else:
                dp2[i+1][j] = dp2[i][j]

    res = 0
    for i in range(n):
        for j in range(t):
            res = max(res,dp1[i][j]+f[i][1]+dp2[n-1-i][t-1-j])

    return res




print(main())
### BUGGY CODE ###

K, S = map(int, input().split())

ans = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                ans += 1
print(ans)

### FIXED CODE ###

K, S = map(int, (input().split()))
cnt = 0
for x in range(K+1):
    for y in range(K+1):
        if 0 <= S-(x+y) <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

N = int(input())
A = list(map(int, input().split(" ")))
dp = dict()
mod = 10 ** 9 + 7

def f(i, ma, mi):
    if i == N:
        return 1
    if (i, ma, mi) in dp:
        return dp[(i, ma, mi)]
    ans = 0
    # iがr, b, gを被って矛盾がないかを見ていく
    if A[i] == ma:
        ans += f(i + 1, ma + 1, mi)
    if A[i] == mi:
        if ma > mi + 1:
            ans += f(i + 1, ma, mi + 1)
        else:
            ans += f(i + 1, mi + 1, ma)
    if A[i] == i - ma - mi:
        ans += f(i + 1, ma, mi)

    dp[(i, ma, mi)] = ans % mod
    return dp[(i, ma, mi)]

print(f(0, 0, 0) % mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

N = int(input())
A = list(map(int, input().strip().split(" ")))
dp = {i: dict() for i in range(N)}
mod = 10 ** 9 + 7

def f(i, ma, mi):
    if i == N:
        return 1
    if (ma, mi) in dp[i]:
        return dp[i][(ma, mi)]
    if A[i] != ma and A[i] != mi and A[i] != i - ma - mi:
        dp[i][(ma, mi)] = 0
        return 0

    ans = 0
    # iがr, b, gを被って矛盾がないかを見ていく
    if A[i] == ma:
        ans += f(i + 1, ma + 1, mi)
    if A[i] == mi:
        if ma > mi + 1:
            ans += f(i + 1, ma, mi + 1)
        else:
            ans += f(i + 1, mi + 1, ma)
    if A[i] == i - ma - mi:
        ans += f(i + 1, ma, mi)

    dp[i][(ma, mi)] = ans % mod
    return ans % mod

print(f(0, 0, 0) % mod)
### BUGGY CODE ###

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

mod = 10**9 + 7

pows = [pow(2, i, mod) for i in range(60)]
count = [0]*60
num = [0]*60
ans = 0

for i in range(n):
    bit = a[i]
    for g in range(60):
        if bit % 2 == 1:
            count[g] += 1
            num[g] += i+1 - count[g]
        else:
            num[g] += count[g]
        bit //= 2

for i in range(60):
    ans += num[i]*pows[i]

print(ans % mod)

### FIXED CODE ###

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

mod = 10**9 + 7

pows = [pow(2, i, mod) for i in range(60)]
count = [0]*60

for i in range(n):
    bit = a[i]
    for g in range(60):
        count[g] += bit%2
        bit //= 2
        if bit == 0:
            break

ans = 0
num = [0]*60

for i in range(n):
    bit = a[i]
    for g in range(60):
        if bit % 2 == 1:
            num[g] += n - count[g]
        else:
            num[g] += count[g]
        bit //= 2

for i in range(60):
    ans += num[i]*pows[i]

print(ans//2 % mod)
### BUGGY CODE ###

def intinput(): return map(int,input().split())

def ab(i):
    global c,l,x
    while len(l[i])>0:
        try:
            x[l[i][0]]=c.pop(0)
            l[l[i][0]].remove(i)
            ab(l[i][0])
            l[i].pop(0)
        except:
            pass
    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000) 

def intinput(): return map(int,input().split())

def ab(i):
    global c,l,x
    while len(l[i])>0:
        x[l[i][0]] = c.pop(0)
        l[l[i][0]].remove(i)
        ab(l[i][0])
        l[i].pop(0)
    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))


lisab = sorted(a+b for a in lisa for b in lisb)[:-k-1:-1]
lisabc = sorted(ab+c for ab in lisab[:k] for c in lisc)[:-k-1:-1]

print(*lisabc, sep="\n")

### FIXED CODE ###

import sys
input = sys.stdin.readline

x,y,z,k = map(int,input().split())
lisa = sorted(map(int,input().split()))
lisb = sorted(map(int,input().split()))
lisc = sorted(map(int,input().split()))

ab = sorted(a+b for a in lisa for b in lisb)[:-k-1:-1]
abc = sorted(ab+c for ab in ab[:k] for c in lisc)[:-k-1:-1]

print(*abc, sep="\n")
### BUGGY CODE ###

N,Q = map(int,input().split())
S = list(input())
num = []

for i in range(len(S)-1):
    if (S[i] +S[i+1] == 'AC'):
        num.append(i+1)

for j in range(Q):
    lq,rq = map(int,input().split())
    count = 0
    for k in num:
        if lq <= k and (k+1) <= rq:
            count += 1 
    print(count)

### FIXED CODE ###

"""
N,Q = map(int,input().split())
S = input()

for i in range(Q):
    lq,rq = map(int,input().split())
    s = S[lq-1:rq]
    count = 0
    while(s.find('A') != -1):
        j = s.find('A')
        if(s[j:j+2] == 'AC'):
            count+=1
            s = s[j+2:]
        else:
            s = s[j+1:]
    print(count)
"""
#愚直なやり方だとTLEになってしまう。
#累積和とよばれるテクニックを使う
#https://qiita.com/drken/items/56a6b68edef8fc605821#問題-3-atcoder-abc-122-c---get-ac

N,Q = map(int,input().split())
S = input()

#区間配列
a = [0] * len(S)
#累積和配列
s = [0] * (len(S) +1)

#左がAである文字Cは何番目にあるか求める
for i in range(len(S)):
    if S[i] == 'C':
        if S[i-1] == 'A':
            a[i] = 1 #i番目に'AC'のCがある (添字が0から始まるため実際にはi-1番目 i番目は'A')

#累積和を計算する
for i in range(1,len(a)+1):
    s[i] = s[i-1] + a[i-1]

#区間内にその文字があるか求める

for i in range(Q):
    lq,rq = map(int,input().split())
    print(s[rq] - s[lq])
### BUGGY CODE ###

#b問題
n=int(input())
ans=1
a=list(int(y) for y in input().split())
# print(a)
if 0 in a:
    print(0)
else:
    for i in range(n):
        ans*=a[i]
        if ans>10**18:
            ans=-1
    print(ans)

### FIXED CODE ###

#b問題
n=int(input())
ans=1
a=list(int(y) for y in input().split())
# print(a)
if 0 in a:
    print(0)
else:
    for i in range(n):
        ans*=a[i]
        if ans>10**18:
            ans=-1
            break
    print(ans)
### BUGGY CODE ###

k=int(input())

import math
import functools 
import itertools

res=0

l=range(1,k+1)

for i in itertools.product(l, repeat=3):
    new_l = list(set(i))
    if len(new_l)==1:
        res+=int(new_l[0])
    else:
        res+=functools.reduce(math.gcd,new_l)

print(res)

### FIXED CODE ###

k=int(input())

from math import gcd
 
res=0
 
for n in range(1,k+1):
    for i in range(1,k+1):
        for j in range(1,k+1):

            res+=gcd(gcd(n,i),j)

print(res)
### BUGGY CODE ###

from collections import deque
import sys


H, W = [int(_) for _ in input().split()]

M = []
queues = []
for i in range(H):
    A = input()
    M.append(A)
    for j in range(W):
        if A[j] == '#':
            queues.append(deque([[j, i, 0]]))

visited = [[False for _ in range(W)] for _ in range(H)]

max_count = 0
while True:
    for q in queues:
        if len(q) == 0:
            continue
        p = q.popleft()
        x = p[0]
        y = p[1]
        count = p[2]
        max_count = max(max_count, count)
        cands = []
        if x - 1 >= 0:
            cands.append([x-1, y])
        if x + 1 < W:
            cands.append([x+1, y])
        if y - 1 >= 0:
            cands.append([x, y-1])
        if y + 1 < H:
            cands.append([x, y+1])
        for cx, cy in cands:
            if M[cy][cx] == '.' and not visited[cy][cx]:
                q.append([cx, cy, count+1])
                visited[cy][cx] = True
    if len([q for q in queues if len(q) == 0]) == len(queues):
        print(max_count)
        break


### FIXED CODE ###

from collections import deque
import sys


H, W = [int(_) for _ in input().split()]

M = []
q = deque([])
for i in range(H):
    A = input()
    M.append(list(A))
    for j in range(W):
        if A[j] == '#':
            q.append([j, i, 0])

depth_now = 0
depth = 0
count = 0
while len(q) > 0:
    p = q.popleft()
    x = p[0]
    y = p[1]
    depth = p[2]
    if x - 1 >= 0 and M[y][x-1] == '.':
        q.append([x-1, y, depth+1])
        M[y][x-1] = '#'
    if x + 1 < W and M[y][x+1] == '.':
        q.append([x+1, y, depth+1])
        M[y][x+1] = '#'
    if y - 1 >= 0 and M[y-1][x] == '.':
        q.append([x, y-1, depth+1])
        M[y-1][x] = '#'
    if y + 1 < H and M[y+1][x] == '.':
        q.append([x, y+1, depth+1])
        M[y+1][x] = '#'
print(depth)
### BUGGY CODE ###

def warshall_floyd(V, E):
    INF = 10 ** 10
    d = [[INF for j in range(V)] for i in range(V)]
    for i, j, c in E:
        d[i - 1][j - 1] = c
        d[j - 1][i - 1] = c
    for k in range(V):
        for i in range(V - 1):
            for j in range(i, V):
                dk = d[i][k] + d[k][j]
                if d[i][j] > dk:
                    d[i][j] = dk
                    d[j][i] = dk
    return d

N = int(input())
E = [list(map(int, input().split())) for _ in range(N - 1)]
d = warshall_floyd(N, E)

Q, K = map(int, input().split())
for i in range(Q):
    x, y = map(int, input().split())
    print(d[x - 1][K - 1] + d[K - 1][y - 1])


### FIXED CODE ###

def dfs(i, V, E):
    S = [i]
    while(len(S) > 0):
        vi = S.pop()
        d = V[vi]
        for j, value in E[vi].items():
            if V[j] > value + d:
                V[j] = value + d
                S.append(j)
    return V

INF = 10 ** 14
n = int(input())
V = [INF for _ in range(n + 1)]
E = [{} for _ in range(n + 1)]
for i in range(n - 1):
    ai, bi, ci = map(int, input().split())
    E[ai][bi] = ci
    E[bi][ai] = ci

q, k = map(int, input().split())
z = [list(map(int, input().split())) for _ in range(q)]
V[k] = 0

V = dfs(k, V, E)
for i in range(q):
    x, y = z[i]
    print(V[x] + V[y])
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
mae = 1
for i in range(k):
    mae *= a[i]
#print(mae)
for j in range(k,n):
    #print(a[j-k],a[j])
    if mae < (mae // a[j-k]) * a[j]:
        print('Yes')
    else:
        print('No')
    mae = (mae // a[j-k]) * a[j]

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
for j in range(k,n):
    if a[j-k] < a[j]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

INFTY = 10**12
def wf(H):
    d = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
    for i in range(1,N+1):
        d[i][i] = 0
        if i in H:
            for x in H[i]:
                j,c = x[0],x[1]
                d[i][j] = c
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
G = {}
for _ in range(M):
    A,B,C = map(int,input().split())
    if A not in G:
        G[A] = []
    G[A].append((B,C))
    if B not in G:
        G[B] = []
    G[B].append((A,C))
d1 = wf(G)
F = {}
for i in range(1,N):
    for j in range(i+1,N+1):
        if d1[i][j]<=L:
            if i not in F:
                F[i] = []
            F[i].append((j,1))
            if j not in F:
                F[j] = []
            F[j].append((i,1))
d2 = wf(F)
Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())
    if d2[s][t]<INFTY:
        print(d2[s][t]-1)
    else:
        print(-1)

### FIXED CODE ###

INFTY = 10**12
def wf(H):
    d = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
    for i in range(1,N+1):
        d[i][i] = 0
        if i in H:
            for x in H[i]:
                j,c = x[0],x[1]
                d[i][j] = c
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
G = {}
for _ in range(M):
    A,B,C = map(int,input().split())
    if A not in G:
        G[A] = []
    G[A].append((B,C))
    if B not in G:
        G[B] = []
    G[B].append((A,C))
d1 = wf(G)
F = {}
for i in range(1,N):
    for j in range(i+1,N+1):
        if d1[i][j]<=L:
            if i not in F:
                F[i] = []
            F[i].append((j,1))
            if j not in F:
                F[j] = []
            F[j].append((i,1))
d2 = wf(F)
Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())
    if d2[s][t]<INFTY:
        print(d2[s][t]-1)
    else:
        print(-1)
### BUGGY CODE ###

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

tree = {}
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a] = tree.get(a, []) + [b]

count = [0] * (N + 1)
for i in range(Q):
    p, x = map(int, input().split())
    count[p] += x

stack = [1]
while stack:
    label = stack.pop()
    if tree.get(label):
        for next_label in tree[label]:
            count[next_label] += count[label]
        stack += tree[label]

ans = count[1:]
print(*ans)


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline()[:-1]


def dfs(tree: dict, count: list) -> list:
    res = [0] * (N + 1)

    stack = [1]
    while stack:
        label = stack.pop()
        res[label] = count[label]
        if tree[label] != []:
            for next_label in tree[label]:
                count[next_label] += count[label]
            stack += tree[label]

    return res


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

tree = {}
for i in range(1, N + 1):
    tree[i] = []
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a] += [b]

count = [0] * (N + 1)
for i in range(Q):
    p, x = map(int, input().split())
    count[p] += x

ans = dfs(tree, count)
print(*ans[1:])
### BUGGY CODE ###

N = int(input())
X = tuple(int(x) for x in input().split())
length = len(X)
for x in range(length):
 print(sorted(X[:x]+X[x+1:])[length//2-1])

### FIXED CODE ###

N = int(input())
X = tuple(int(x) for x in input().split())
length = len(X)
med = sorted(X)[length//2-1:length//2+1]
for x in X:
 print(med[1] if x < sum(med)/2 else med[0])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
 
s = 0
for i in range(N):
  s += A[i]
  s %= (10**9+7)
s = s**2
s %= (10**9+7)
 
t = 0
for i in range(N):
  t += (A[i]**2 % (10**9+7))
t %= (10**9+7)

ans = (s-t) % (10**9+7)
tmp = (2**1000000005) % (10**9+7)
ans *= tmp
ans %= (10**9+7)
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
s = 0
for i in range(N):
  s += A[i]
  s %= (10**9+7)
s = s**2
s %= (10**9+7)
 
t = 0
for i in range(N):
  t += (A[i]**2 % (10**9+7))
t %= (10**9+7)
 
ans = (s-t) % (10**9+7)
'''
tmp = (2**1000000005) % (10**9+7)
'''
tmp = 500000004
ans *= tmp
ans %= (10**9+7)
print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
result = [0 for _ in range(n)]
t = [None for _ in range(n)]
prev = ''
for i in range(n):
  if t[i] is not None:
    continue
  if prev == 'R' and s[i] == 'L':
    j = i
    while t[j] == 'L' and j < n:
      t[j] = (j - (i - 1), i - 1)
      j = i + 1
    j = i - 1
    while t[j] == 'R' and j > 0:
      t[j] = (j - (i - 1), i - 1)
      j = i - 1
for i in range(n):
  p = i
  if s[p] == 'R':
    p += 1
    prev = 'R'
  else:
    p -= 1
    prev = 'L'
  count = 1
  while True:
    if t[p] is not None:
      fp = t[p][0]
      fcount = count + t[p][1]
      t[i] = (fp, fcount)
      if fcount % 2 == 0:
        result[fp] += 1
      else:
        result[fp - 1] += 1
      break
    if s[p] == 'R':
      p += 1
      prev = 'R'
    else:
      if prev == 'R':
        t[i] = (p, count)
        if count % 2 == 0:
          result[p] += 1
        else:
          result[p - 1] += 1
        break
      p -= 1
      prev = 'L'
    count += 1
print(' '.join(map(str, result)))


### FIXED CODE ###

s = input()
n = len(s)
result = [0 for _ in range(n)]
start = 0
c = 'R'
for i in range(1, n):
  if s[i] != c:
    if c == 'R':
      result[i - 1] += (i - start) // 2 + (i - start) % 2
      result[i] += (i - start) // 2
      c = 'L'
    else:
      result[start] += (i - start) // 2 + (i - start) % 2
      result[start - 1] += (i - start) // 2
      c = 'R'
    start = i
result[start] += (n - start) // 2 + (n - start) % 2
result[start - 1] += (n - start) // 2
print(*result)
### BUGGY CODE ###

k = int(input())
temp = 7
juu = 7
for i in range(1, 10**7):
  temp = temp % k
  if temp == 0:
    print(i)
    break
  juu = juu * 10 % k
  temp += juu % k
else:
  print(-1)


### FIXED CODE ###

k = int(input())
temp = 7
juu = 7
for i in range(1, 10**6):
  temp = temp % k
  if temp == 0:
    print(i)
    break
  juu = (juu * 10) % k
  temp += juu % k
else:
  print(-1)
### BUGGY CODE ###

n, k = map(lambda x: int(x), input().split(' '))
a = list(map(lambda x: int(x), input().split(' ')))

num_dups = []
a_set = set(a)
for elem in a_set:
    num_dups.append(a.count(elem))

num_dups.sort(reverse=True)

ball_to_replace = len(a_set) - k

result = 0
for i in range(ball_to_replace):
    result += num_dups.pop()

print(result)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A1 = set(A)
AN = {}
for a in A:
    if not a in AN:
        AN[a] = 0
    AN[a] += 1
AN = sorted(AN.items(), key=lambda x: x[1])
ans = 0
K1 = len(A1) - K
if K1 > 0:
    for k in range(K1):
        ans += AN[k][1]
    print(ans)
else:
    print('0')
### BUGGY CODE ###

import numpy as np
K=int(input())
s=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            s+=np.gcd(a,np.gcd(b,c))
print(s)


### FIXED CODE ###

import numpy as np
K=int(input())
s3=0
s2=0
s1=0
s0=0
for a in range(1,K-1):
    for b in range(a+1,K):
        d=np.gcd(a,b)
        for c in range(b+1,K+1):
            s0+=np.gcd(c,d)
for a in range(1,K):
    for c in range(a+1,K+1):
        s1+=np.gcd(a,c)
for a in range(1,K):
    for b in range(a+1,K+1):
        s3+=np.gcd(a,b)
for k in range(K+1):
    s2+=k
print(s0*6+s1*3+s3*3+s2)
### BUGGY CODE ###

N = int(input().strip())
A = [int(x) for x in input().strip().split(" ")]
Q = int(input().strip())

for q in range(Q):
    B, C = [int(x) for x in input().strip().split(" ")]
    A = [C if a == B else a for a in A]
    print(sum(A))


### FIXED CODE ###

N = int(input().strip())

A = {}
for a in [int(x) for x in input().strip().split(" ")]:
    A.setdefault(a, 0)
    A[a] += 1
total = sum([k * v for k, v in A.items()]) 

Q = int(input().strip())

for q in range(Q):
    B, C = [int(x) for x in input().strip().split(" ")]
    if B in A:
        A.setdefault(C, 0)
        dif = (C - B) * A[B]
        A[C] += A[B]
        del A[B]
        total += dif
    print(total)
### BUGGY CODE ###

#TLE

import sys

INF = float('inf')


input = sys.stdin.readline


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


N, K = LIST()
h = LIST()

# DP配列を初期化
dp = [INF] * N

# 初期条件を入力
dp[0] = 0

# テーブルを更新 もらうDP
for i in range(1, N):
    dp[i] = min([dp[i - j] + abs(h[i] - h[i - j]) for j in range(1, min(K, i) + 1)])

print(dp[N - 1])


### FIXED CODE ###

import sys

INF = float('inf')

input = sys.stdin.readline


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


N, K = LIST()
h = LIST()

# DP配列を初期化
dp = [INF] * N

# 初期条件を入力
dp[0] = 0

# テーブルを更新 もらうDP
for i in range(1, N):
    x = max(0, i - K)
    dp[i] = min([dp_ + abs(h[i] - h_) for dp_, h_ in zip(dp[x:i], h[x:i])])

print(dp[N - 1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


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


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


def main():
    N = II()
    graph = [[] for i in range(N)]
    prev = [-1 for i in range(N)]
    colors = {}
    edges = []
    for _ in range(N-1):
        a, b = MI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        edges.append([a-1, b-1])
    max_edge = 0
    max_edge_idx = -1
    for i in range(len(graph)):
        length = len(graph[i])
        if length >= max_edge:
            max_edge = length
            max_edge_idx = i

    deque = cl.deque([max_edge_idx])
    while len(deque) > 0:
        target = deque.popleft()
        pre = prev[target]
        unused_colors = set(list(range(1, max_edge+1)))
        if pre != -1:
            unused_colors.remove(colors[(target, pre)])

        connecteds = graph[target]

        for connected in connecteds:
            if (target, connected) in colors:
                unused_colors.discard(colors[(connected, target)])
                continue

            color = min(unused_colors)
            colors[(target, connected)] = color
            colors[(connected, target)] = color
            prev[connected] = target
            deque.append(connected)
            unused_colors.remove(color)

    print(max_edge)

    for edge in edges:
        print(colors[(edge[0], edge[1])])


main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


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


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


def main():
    N = II()
    graph = [[] for i in range(N)]
    prev = [-1 for i in range(N)]
    colors = {}
    edges = []
    for _ in range(N-1):
        a, b = MI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        edges.append([a-1, b-1])
    max_edge = 0
    max_edge_idx = -1
    for i in range(len(graph)):
        length = len(graph[i])
        if length >= max_edge:
            max_edge = length
            max_edge_idx = i

    deque = cl.deque([max_edge_idx])
    while len(deque) > 0:
        target = deque.popleft()
        pre = prev[target]
        pre_key = (target, pre) if target < pre else (pre, target)
        used_color = 0
        if pre != -1:
            used_color = colors[pre_key]

        connecteds = graph[target]
        color = 1
        for connected in connecteds:
            key = (target, connected) if target < connected else (
                connected, target)
            if key in colors:
                continue
            if color == used_color:
                color += 1
            colors[key] = color
            prev[connected] = target
            deque.append(connected)
            color += 1

    print(max_edge)

    for edge in edges:
        print(colors[(edge[0], edge[1])])


main()