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

from itertools import combinations
mod = int(1e9+7)
n, m = [int(num) for num in input().split()]

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

sumx = 0
for cmb in combinations(x, 2):
    sumx += (cmb[1] - cmb[0]) % mod

sumy = 0
for cmb in combinations(y, 2):
    sumy += (cmb[1] - cmb[0]) % mod

ans = sumx * sumy % mod

print(ans)

### FIXED CODE ###

# 予めsx, syを全て計算しておく
# このとき漸化式を使えば毎回全ての話を求める必要がない

mod = int(1e9+7)
n, m = [int(num) for num in input().split()]

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


sx = [0] * n
sx[0] = x[0]
for i in range(n-1):
    sx[i+1] = sx[i] + x[i+1]
sxd = 0  
for i in range(n-1):
    sxd += ((sx[n-1] - sx[i]) - x[i] * ((n-1) - (i+1) + 1)) % mod

sy = [0] * m
sy[0] = y[0]
for k in range(m-1):
    sy[k+1] = sy[k] + y[k+1]
syd = 0
for k in range(m-1):
    syd += ((sy[m-1] - sy[k]) - y[k] * ((m-1) - (k+1) + 1)) % mod

ans = ((sxd % mod) * (syd % mod)) % mod

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

import sys
input = sys.stdin.readline


a, b, c= map(int, input().split())
t_7 = 2/7

f_table = [a*t//b for t in range(b)]

if c >= b:
    print(f_table[-1])

else:
    x = c
    c_amari = c%b
    c_sho = c//b
    ans =f_table[c_amari]
    print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline


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


#f_table = [a*t//b for t in range(b)]

if c >= b:
    print((a * (b-1)) // b)

else:
    x = c
    c_amari = c%b
    c_sho = c//b
    ans =(a * c_amari) //b
    print(ans)
### BUGGY CODE ###

n, s = int(input()), input()
sm = 0
for i in range(n - 2):
    for j in range(i, n - 1):
        for k in range(j, n):
            if k != 2 * j - i and s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                sm += 1
print(sm)


### FIXED CODE ###

n, s = int(input()), input()
a = ["R", "G", "B"]
cnt = [0, 0, 0]
for i in s:
    cnt[a.index(i)] += 1
c = cnt[0] * cnt[1] * cnt[2]
for i in range(1, n-1):
    for j in range(i+1, n):
        k = 2 * j - i
        if j-1 < k-1 < n:
            if s[i-1] != s[j-1] and s[j-1] != s[k-1] and s[k-1] != s[i-1]:
                c -= 1

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

[n,k] = list(map(int,input().split()))
li = list(map(int,input().split()))

point = []

for i in range(n-k+1):
    point_new = 1
    #for j in range(i,k+i):
        #point_new *= li[j]
    point.append(sum(li[i:k+i]))
    
for i in range(1,len(point)):
    if point[i] > point[i-1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

[n,k] = list(map(int,input().split()))
li = list(map(int,input().split()))

orl = li[0]

for i in range(1,n-k+1):
    in_num = li[i+k-1]
    if in_num>orl:
        print('Yes')
    else:
        print('No')
    orl = li[i]
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input())
for i in range(1,N+1):
  cnt=0
  listx=list(range(1,i-2))
  for x in listx:
    for y in range(1,i-x+1):
      for z in range(1,i-x-y+1):
        if i==x**2+y**2+z**2+x*y+y*z+z*x:
          cnt+=1
  print(cnt)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import math

N=int(input())
ans=[0]*(N+1)
sn=int(math.sqrt(N)+1)
for x in range(1,sn+1):
  for y in range(1,sn+1):
    for z in range(1,sn+1):
      i=x**2+y**2+z**2+x*y+y*z+z*x
      if 1<=i<=N:
        ans[i]+=1
for h in range(1,N+1):          
  print(ans[h])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, L: "List[int]"):
    L.sort()

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            from bisect import bisect_left, bisect_right
            k = bisect_left(L, L[i]+L[j])
            ans += max(0, k-(j+1))

    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

from bisect import bisect_left, bisect_right



def solve(N: int, L: "List[int]"):
    ans = 0
    L.sort()

    for x in range(N):
        for y in range(x+1,N):
            ze = bisect_left(L, L[x]+L[y])            
            ans += (ze-y-1)
            
    print(ans)

    return
 


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

#

n=int(input())
l = [int(input()) for _ in [0] * n]
x = 0
for i in range(n):
    y = l[:]
    y.pop(i)
    print(max(y))


### FIXED CODE ###

n=int(input())
l = [int(input()) for _ in [0] * n]
m = sorted(l)
a = m[-1]
b = m[-2]
#print(a,b)
for i in range(n):
    if l[i] == a:
        print(b)
    else:
        print(a)
### BUGGY CODE ###

from math import factorial

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

def comb(n,r):
  return factorial(n) / (factorial(r) * factorial(n-r)) if n >= r else 0

if K%2 == 1:
  cand = N // K
  print(int(cand + comb(cand,2) * 6 + comb(cand,3) * 6))
else:
  cand_mod0 = N // K
  ans_mod0 = cand_mod0 + comb(cand_mod0, 2) * 6 + comb(cand_mod0, 3) * 6
  cand_modhalf = N // K if N % K < K / 2 else (N // K) + 1
  ans_modhalf = cand_modhalf + comb(cand_modhalf, 2) * 6 + comb(cand_modhalf, 3) * 6
  print(int(ans_mod0 + ans_modhalf))

### FIXED CODE ###

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

if K%2 == 1:
  cand = N // K
  ans = cand\
      + cand * (cand-1) * 3\
      + cand * (cand-1) * (cand-2)
  print(int(ans))
else:
  cand_mod0 = N // K
  ans_mod0 = cand_mod0\
           + cand_mod0 * (cand_mod0-1) * 3\
           + cand_mod0 * (cand_mod0-1) * (cand_mod0-2)
  cand_modhalf = N // K if N % K < K / 2 else (N // K) + 1
  ans_modhalf = cand_modhalf\
           + cand_modhalf * (cand_modhalf-1) * 3\
           + cand_modhalf * (cand_modhalf-1) * (cand_modhalf-2)
  print(int(ans_mod0 + ans_modhalf))
### BUGGY CODE ###

N=int(input())
A=[0]*N
shougen=[[] for i in range(0,N)]
for i in range(0,N):
    A[i]=int(input())
    for j in range(0,A[i]):
        a,b=map(int,input().split())
        shougen[i].append([a,b])
m=0
for i in range(0,2**N):
    flag=0
    check=[]
    for j in range(0,N):
        if i>>j & 1==1:
            check.extend(shougen[j])
    for j in range(0,N):
        if ([j+1,0] in check) or ([j+1,1] in check):
            if [j+1,0] in check:
                if j==0:
                    data=[0]
                else:
                    data.append(0)
            if [j+1,1] in check:
                if j==0:
                    data=[1]
                else:
                    data.append(1)

        else:
            if j==0:
                data=[2]
            else:
                data.append(2)
    for j in range(0,N):
        if data[j]!=2:
            if int(data[j])!=(i>>j)%2 :
                flag=1
    if len(data)!=N:
        flag=1
    if flag==0:
        test=sum(i>>j &1 for j in range(0,N))
        if test>m:
            m=test

print(m)


### FIXED CODE ###

N=int(input())
shougen=[(0,0) for i in range(0,N)]
for i in range(0,N):
    A=int(input())
    honest=0
    unkind=0
    for j in range(0,A):
        x,y=map(int,input().split())
        if y==0:
            unkind+=2**(x-1)
        else:
            honest+=2**(x-1)
    shougen[i]=(honest,unkind)

ans=0
for i in range(0,2**N):
    honest=i
    unkind=2**N-1-i
    check=True
    test=0
    for j in range(0,N):
        if (i>>j)&1 ==1:
            test+=1
            x,y=shougen[j]
            if (honest-x)^x!=honest or (unkind-y)^y!=unkind:
                check=False
    if check:
        if test>ans:
            ans=test

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

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

for p in range(n):
    i = p + 1
    while i < n:
        if a[p] == a[i]:
            y = False
            break
        i += 1
        
if y:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

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

for i in range(n - 1):
    if a[i] == a[i + 1]:
        y = False
        break
        
if y:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

from operator import mul
from functools import reduce
def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
n = int(input())
a_ls = list(map(int, input().split()))
num_total = max(a_ls)
a_ls.remove(num_total)
Max = 0
for a in a_ls:
    c = combinations_count(num_total,a)
    if Max <= c:
        Max = c
        r = a
print(num_total,r)
    

### FIXED CODE ###

n = int(input())
a_ls = list(map(int, input().split()))
if n > 2:
    a_ls.sort()
    num_total = a_ls[-1]
    a_ls.pop()
    def isOK(index, key, l):
        if l[index] >= key:
            return True
        else:
            return False
    def meguru_search(l, key):
        '''
        key以上の値を持つ最小のインデックスを返す
        '''
        left = -1
        right = len(l)

        while (right - left) > 1:
            mid = left + (right - left) // 2
            # 直感的に記憶　
                # 「含まれている」んだったら「含むを許容（等号付き）する右側」はmidまで動かして問題ない
                    # 新しいrightの位置がkeyの位置だとしても、「含む」は許容されてる
                # 「含まれていない」んだったら「含まない(<)左の壁」をそこまで動かしてもkeyを通り過ぎることはない
            if isOK(mid, key, l):
                right = mid
            else:
                left = mid
        
        # whileを抜ける時、rightとleftは一個差で、かつkeyがrightの位置にある
        return right

    if num_total % 2 == 0:
        Max = num_total // 2
    else:
        Max = num_total // 2 + 1
    Maxind1 = meguru_search(a_ls, Max)
    Maxind2 = Maxind1 - 1
    abs_1 = abs(Max - a_ls[Maxind1])
    abs_2 = abs(Max - a_ls[Maxind2])
    if abs_1 > abs_2:
        r = a_ls[Maxind2]
    else:
        r = a_ls[Maxind1]
    print(num_total, r)
else:
    print(max(a_ls), min(a_ls))
### BUGGY CODE ###

import numpy as np
N,W=map(int,input().split())
A = [list(map(int, input().split())) for i in range(N)]



dp=np.zeros((N+1,W+1))


for i in range(N):
    for w in range(W+1):
        if w>=A[i][0]:
            dp[i+1][w] = max([dp[i][w-A[i][0]]+A[i][1], dp[i][w]])
        else:
            dp[i+1][w] = dp[i][w]
        
print(int(dp[N][W]))

### FIXED CODE ###

N,W=map(int,input().split())
A = [list(map(int, input().split())) for i in range(N)]



dp = [[0 for i in range(W+1)] for j in range(N+1)]


for i in range(N):
    for w in range(W+1):
        if w>=A[i][0]:
            dp[i+1][w] = max([dp[i][w-A[i][0]]+A[i][1], dp[i][w]])
        else:
            dp[i+1][w] = dp[i][w]
        
print(int(dp[N][W]))
### BUGGY CODE ###

n = int(input())
anagrams = ["".join(sorted(input())) for i in range(n)]

from scipy.misc import comb
print(sum([comb(anagrams.count(word), 2, exact=True)\
          for word in set(anagrams)]))

### FIXED CODE ###

n = int(input())
anagrams = ["".join(sorted(input())) for i in range(n)]
from collections import defaultdict
d = defaultdict(list)
for i in range(n):
    d[anagrams[i]].append(i)
from scipy.misc import comb
cnt=0
for k, v in d.items():
    cnt+=comb(len(v), 2, exact=True)
print(cnt)
### BUGGY CODE ###

from heapq import heappush, heappop
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
c = [list(input()) for _ in range(h)]
# print(x1, y1)
# print(x2, y2)

dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
MAX = 10**7
dp = [[[(MAX, MAX)] * 4 for _ in range(w)] for _ in range(h)]

q = [((1, 0, x1, y1, i)) for i in range(4)]

while q:
    c1, c2, x, y, d = q.pop()
    # print(x, y, d, c1, c2)
    if c1 > dp[x][y][d][0]:
        continue
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if c[nx][ny] == '@':
            continue
        if i == d and c2 < k:
            if dp[nx][ny][i] > (c1, c2 + 1):
                dp[nx][ny][i] = (c1, c2 + 1)
                q.append(((c1, c2 + 1, nx, ny, i)))
        else:
            if dp[nx][ny][i] > (c1 + 1, 1):
                dp[nx][ny][i] = (c1 + 1, 1)
                q.append(((c1 + 1, 1, nx, ny, i)))

ans = min(dp[x2][y2][i][0] for i in range(4))
if ans == MAX:
    ans = -1
print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
c_ = [tuple(input()) for _ in range(h)]
c = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if c_[i][j] == '@':
            c[i][j] = True
# print(x1, y1)
# print(x2, y2)

dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
MAX = 10**7


def convert(x, y, d):
    return (x * w + y) * 4 + d


# dp = [[[(MAX, MAX)] * 4 for _ in range(w)] for _ in range(h)]
dp = [MAX * (k + 1) + k] * (h * w * 4)

# q = [((1, 0, x1, y1, i)) for i in range(4)]
q = [((k + 1, convert(x1, y1, i))) for i in range(4)]

while q:
    c0, xyd = heappop(q)
    c1 = c0 // (k + 1)
    c2 = c0 % (k + 1)
    # print(x, y, d, c1, c2)
    d = xyd % 4
    y = (xyd // 4) % w
    x = (xyd // 4) // w
    if c1 > dp[xyd] // (k + 1):
        continue
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        nxyi = convert(nx, ny, i)
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if c[nx][ny]:
            continue
        if i == d and c2 < k:
            if dp[nxyi] > c1 * (k + 1) + c2 + 1:
                dp[nxyi] = c1 * (k + 1) + c2 + 1
                heappush(q, (dp[nxyi], nxyi))
        else:
            if dp[nxyi] > (c1 + 1) * (k + 1) + 1:
                dp[nxyi] = (c1 + 1) * (k + 1) + 1
                heappush(q, (dp[nxyi], nxyi))

ans = min(dp[convert(x2, y2, i)] // (k + 1) for i in range(4))
if ans == MAX:
    ans = -1
print(ans)
### BUGGY CODE ###

n = int(input())
s = []
for _ in range(n):
    sw = input()
    s.append([c for c in sw])

def allequal(s):
    for i in range(n):
        for j in range(n):
            if s[i][j] != s[0][0]:
                return False
    return True

def val(s,k):
    global n
    for i in range(n):
        if i+k >= n:
            ni = i+k-n
        else:
            ni = i+k
        for j in range(n):
            if j-k < 0:
                nj = j-k+n
            else:
                nj = j-k
            if s[i][j] != s[nj][ni]:
                return False
    return True

if allequal(s):
    print(n**2)
else:
    res = 0
    for k in range(0,n):
        if val(s,k):
            res += n
    print(res)

### FIXED CODE ###

n = int(input())
s = []
for _ in range(n):
    s.append(input())
st=list(map(''.join,zip(*s)))

def plusa(s,a):
    ns = []
    for ss in s:
        ns.append(ss[a:]+ss[:a])
    return ns

def plusb(s,b):
    global n
    ns = []
    for i in range(n-b):
        ns.append(s[b+i])
    for i in range(b):
        ns.append(s[i])
    return ns

res = 0
for i in range(n):
    if plusa(st,i) == plusb(s,i):
        res += n

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

n=int(input())
a=list(map(int,input().split()))
data=[]
s=set(a)
for i in s:
  if 2<=a.count(i)<4:
    data.append(i)
  elif 4<=a.count(i):
    data.append(i)
    data.append(i)
data.sort(reverse=True)
if len(data)==0 or len(data)==1:
  print(0)
else:
  print(data[0]*data[1])

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
A=Counter(a)
s=set(a)
S=sorted(list(s))
S.reverse()
h=0
w=0
for i in S:
  res=A[i]
  if res>=4:
    if h==0:
      h=i
    if w==0:
      w=i
  elif 2<=res<4:
    if w==0:
      w=i
    elif w!=0 and h==0:
      h=i
print(h*w)
### BUGGY CODE ###

from sys import stdin

h,n = [int(x) for x in stdin.readline().rstrip().split()]
a = [0]*n ;b = [0]*n

for i in range(n):
    a[i],b[i] = [int(x) for x in stdin.readline().rstrip().split()]

#最高で削られる可能性がある体力
H = max(a)

inf = 10**10

#体力をちょうどi削るために必要な最低の魔力
dp = [inf for _ in range(h+H+1)];dp[0] = 0

for i,j in zip(a,b):
    for k in range(h+1):
        if dp[k+i] > dp[k] + j:
            dp[k+i] = dp[k] + j

print(min(dp[h:]))

### FIXED CODE ###

from sys import stdin

h,n = [int(x) for x in stdin.readline().rstrip().split()]
a = [0]*n
b = [0]*n

for i in range(n):
    a[i],b[i] = [int(x) for x in stdin.readline().rstrip().split()]

#最高で削られる可能性がある体力
H = max(a)

inf = 10**10

#体力をちょうどi削るために必要な最低の魔力
dp = [inf for _ in range(h+H+1)]
dp[0] = 0

for i in range(n):
    for j in range(h+1):
        if dp[j+a[i]] > dp[j] + b[i]:
            dp[j+a[i]] = dp[j] + b[i]

print(min(dp[h:]))
### BUGGY CODE ###

S=input()
Q=int(input())
for i in range(Q):
  A=list(input().split())
  if len(A)==1:
    S=S[::-1]
  else:
    if int(A[1])==1:
      S=A[-1]+S
    else:
      S=S+A[-1]
print(S)   

### FIXED CODE ###

from collections import deque
S=input()
Q=int(input())
q=deque()
for i in S:
  q.append(i)
cnt=0
for i in range(Q):
  A=list(input().split())
  if int(A[0])==1:
    cnt+=1
  else:
    if int(A[1])==cnt%2+1:
      q.appendleft(A[-1])
    else:
      q.append(A[-1])
if (cnt%2)==0:
  for i in range(len(q)):
    print(q.popleft(),end='')
else:
  for i in range(len(q)):
    print(q.pop(),end='')
### BUGGY CODE ###

n = int(input())
listForA=[]

index=0
while index < n:
    inputN = int(input())
    if inputN in listForA:
        listForA.remove(inputN)
    else:
        listForA.append(inputN)
    index+=1

print(len(listForA))

### FIXED CODE ###

n = int(input())
listForA=[]

index=0
while index < n:
   listForA.append(int(input()))
   index+=1

listForA.sort()
index2 =0
beforeC=""
count=0
allCount=0
while index2 < n:
    if index2==0:
        beforeC=listForA[index2]
        count=1
    else:
        if beforeC == listForA[index2]:
            count+=1
        else:
            if count%2==1:
                allCount+=1
            beforeC = listForA[index2]
            count=1
    index2+=1
if count%2==1:
    allCount+=1

print(allCount)
### BUGGY CODE ###

import sys

inp = sys.stdin
# inp = open("testdata.txt", "r")
def input():
	return inp.readline().strip()

n, m, l = map(int, input().split())

adjl = [[0 if i==j else float('inf') for j in range(n)] for i in range(n)]

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

for k in range(n):
	for i in range(n):
		for j in range(n):
			adjl[i][j] = min(adjl[i][j], adjl[i][k]+adjl[k][j])

old_adjl = [[ele for ele in row] for row in adjl]

for i in range(n):
	for j in range(n):
		if i==j: adjl[i][j] = 0
		else: adjl[i][j] = 1 if old_adjl[i][j] <= l else float("inf")

for k in range(n):
	for i in range(n):
		for j in range(n):
			if i==k or k==j:
				continue
			adjl[i][j] = min(adjl[i][j], adjl[i][k]+adjl[k][j])

q = int(input())

for _ in range(q):
	a, b = map(int, input().split())
	ans = adjl[a-1][b-1]
	print(-1 if ans==float("inf") else ans-1)

### FIXED CODE ###

import sys

inp = sys.stdin
# inp = open("testdata.txt", "r")
def input():
	return inp.readline().strip()

	
n, m, l = map(int, input().split())

def warshall_floyd(d):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j] = min(d[i][j],d[i][k] + d[k][j])
	return d

adjl = [[float('inf') for j in range(n)] for i in range(n)]
for i in range(n):
	adjl[i][i] = 0

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

adjl = warshall_floyd(adjl)

for i in range(n):
	for j in range(n):
		if i==j: adjl[i][j] = 0
		else: adjl[i][j] = 1 if adjl[i][j] <= l else float("inf")

adjl = warshall_floyd(adjl)

q = int(input())

for _ in range(q):
	a, b = map(int, input().split())
	ans = adjl[a-1][b-1]
	print(-1 if ans==float("inf") else ans-1)
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(100000)
INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]

def dfs(x, y, m):
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    if y > N :
        return 0
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]

while True:
    mem = [[[INF for i in range(150)] for j in range(153)] for k in range(100)]
    N, M = map(int, input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    print(dfs(0, 0, M))

### FIXED CODE ###

INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
 
def dfs(x, y, m):
    if y > N :
        return 0
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]
 
while True:
    N, M = map(int, raw_input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, raw_input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    mem = [[[INF for i in range(M + 1)] for j in range(N + 1)] for k in range(N + 4)]
    print(dfs(0, 0, M))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(5000)


def dfs(v, parent, rest, edge):
    ret = 0
    for c in edge[v]:
        if c != parent:
            ret += dfs(c, v, rest - 1, edge)
    return ret + (rest <= 0)


def main(N, K, edge):
    ans = N
    if K % 2 == 0:
        for v in range(N):
            ans = min(ans, sum(dfs(c, v, K // 2, edge) for c in edge[v]))
    else:
        for v in range(N):
            for c in edge[v]:
                ans = min(ans, dfs(v, c, K // 2 + 1, edge) + dfs(c, v, K // 2 + 1, edge))
    print(ans)


if __name__ == '__main__':
    N, K = map(int, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        u, v = u - 1, v - 1
        edge[u].append(v)
        edge[v].append(u)
    main(N, K, edge)


### FIXED CODE ###

import sys
sys.setrecursionlimit(5000)


def dfs(v, parent, rest, edge):
    ret = 0
    for c in edge[v]:
        if c != parent:
            ret += dfs(c, v, rest - 1, edge)
    return ret + (rest <= 0)


def main(N, K, edge):
    ans = N
    if K % 2 == 0:
        for v in range(N):
            ans = min(ans, sum(dfs(c, v, K // 2, edge) for c in edge[v]))
    else:
        for v in range(N):
            for c in edge[v]:
                ans = min(ans, dfs(v, c, K // 2 + 1, edge) + dfs(c, v, K // 2 + 1, edge))
    print(ans)


if __name__ == '__main__':
    N, K = map(int, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        u, v = u - 1, v - 1
        edge[u].append(v)
        edge[v].append(u)
    main(N, K, edge)