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

import sys;input=sys.stdin.readline
N, = map(int, input().split())
S = []
for _ in range(N):
    s = input().strip()
    S.append(s)
S.sort(key=lambda x:len(x))
D = dict()
dd = set()
R = 0
for s in S:
    l = len(s)
    d = [0]*26
    for c in dd:
        d[c] += 1
    mm = 0
    xs = []
    for i in range(l-1, -1, -1):
        cc = ord(s[i]) - 97
        xs.append(s[i])
        R += d[cc]
        d[cc] = 0
        tmp = "".join(xs)
        if tmp in D:
            for c in D[tmp]:
                d[c] += 1
        if i == 0:
            f = cc
        if i == 1:
            nn = tmp
        mm += 1
    if l != 1:
        if nn not in D:
            D[nn] = set()
        D[nn].add(f)
    else:
        dd.add(f)
print(R)


### FIXED CODE ###

import sys;input=sys.stdin.readline
N, = map(int, input().split())
MOD=67280421310721
S = []
for _ in range(N):
    s = input().strip()
    S.append(s)
S.sort(key=lambda x:len(x))
D = dict()
dd = set()
R = 0
for s in S:
    l = len(s)
    d = [0]*26
    for c in dd:
        d[c] += 1
    tmp=0
    for i in range(l-1, -1, -1):
        ee = ord(s[i]) - 97
        tmp = 100*tmp+(ee+1)
        tmp %= MOD
        R += d[ee]
        d[ee] = 0
        if tmp in D:
            for c in D[tmp]:
                d[c] += 1
        if i == 1:
            nn = tmp
    if l != 1:
        if nn not in D:
            D[nn] = set()
        D[nn].add(ee)
    else:
        dd.add(ee)
print(R)
### BUGGY CODE ###

def main():
    N, P = (int(i) for i in input().split())
    S = input()

    ans = 0
    if P == 5 or P == 2:
        for i in range(1):
            for j in range(1, N-i+1):
                num = int(S[i:i+j])
                if num % P == 0:
                    ans += len(S[i:i+j])
    else:
        S = S[::-1]
        d = 1
        acc = [0]*(N+1)
        for i, s in enumerate(S):
            s = int(s)
            acc[i+1] = (s * d + acc[i]) % P
            d *= 10
            d %= P
        from collections import Counter
        c = Counter(acc)
        # print(acc, c)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = [int(s) for s in input()]

    ans = 0
    if P == 5 or P == 2:
        for i, s in enumerate(S, start=1):
            # j文字取る
            if s % P == 0:
                ans += i
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1], start=1):
            # print(i, s)
            acc[i] = (s * d + acc[i-1]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


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

n = int(input())
list_a = list(map(int, input().split()))
q = int(input())
ans = sum(list_a)

for i in range(q):
    b, c = map(int, input().split())
    count = list_a.count(b)
    list_a = [c if i == b else i for i in list_a]
    ans += count * (c-b)

    print(ans)


### FIXED CODE ###

import numpy as np

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

counts = np.zeros(100000, dtype=int)

ans = 0

for i in range(len(list_a)):
    counts[list_a[i]-1] += 1
    ans += list_a[i]

q = int(input())

for i in range(q):
    b, c = map(int, input().split())

    ans += counts[b-1] * (c - b)

    counts[c-1] += counts[b-1]
    counts[b-1] = 0

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

k = int(input())
import math
from functools import reduce

ans = 0

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

for i in range(1,k+1):
    for j in range(1,k+1):
        for s in range(1,k+1):
            ans += gcd(i,j,s)
            
print(ans)

### FIXED CODE ###

from math import gcd

n = int(input())

ans = 0

for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      ans += gcd(gcd(i,j),k)
      
print(ans)
### BUGGY CODE ###

n = int(input())

s = list(input())

res = 0

s_dif_g = [0]*n
s_dif_r = [0]*n
s_dif_b = [0]*n

for i in range(n):
    s_dif_r[i] = s[i::].count('R')
    s_dif_g[i] = s[i::].count('G')
    s_dif_b[i] = s[i::].count('B')

sample = ["R","G","B"]
for i in range(n):
    fst = s[i]
    for j in range(i+1,n-1):
        if(s[j] != fst):
            scd = s[j]
            for x in sample:
                if(x != fst and x != scd):
                    if(x == "R"):
                        res += s_dif_r[j+1]
                    if(x == "G"):
                        res += s_dif_g[j+1]
                    if(x == "B"):
                        res += s_dif_b[j+1]
                    if(2*j-i < n):    
                        if(s[2*j-i] == x):
                            res -= 1
            
            

print(res)
    

### FIXED CODE ###

n = int(input())

s = list(input())

res = 0

s_dif_g = [0]*n
s_dif_r = [0]*n
s_dif_b = [0]*n

for i in range(n):
    s_dif_r[i] = s[i::].count('R')
    s_dif_g[i] = s[i::].count('G')
    s_dif_b[i] = s[i::].count('B')

sample = ["R","G","B"]
for i in range(n):
    fst = s[i]
    for j in range(i+1,n-1):
        if(s[j] != fst):
            scd = s[j]
            for x in sample:
                if(x != fst and x != scd):
                    if(x == "R"):
                        res += s_dif_r[j+1]
                    if(x == "G"):
                        res += s_dif_g[j+1]
                    if(x == "B"):
                        res += s_dif_b[j+1]
                    if(2*j-i < n):    
                        if(s[2*j-i] == x):
                            res -= 1
            
            

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

n = int(input())
V = list(map(int,input().split(" ")))
e,o = [],[]

for i,v in enumerate(V):
    if i % 2 == 0:
        e.append(v)
    else:
        o.append(v)

e_ele = list(set(e))
o_ele = list(set(o))
e1,e2 = None,None
o1,o2 = None,None

for val in e_ele:
    if e.count(val) > e.count(e1):
        e1 = val
        continue
    if e.count(val) > e.count(e2):
        e2 = val

for val in o_ele:
    if o.count(val) > o.count(o1):
        o1 = val
        continue
    if o.count(val) > o.count(o2):
        o2 = val

ans = 0
if e1 != o1:
    ans = len(e) - e.count(e1) + len(o) - o.count(o1)
else:
    ans = len(e) - e.count(e1) + len(o) - o.count(o2)
    if ans > len(o) - o.count(o1) + len(e) - e.count(e2):
        ans = len(o) - o.count(o1) + len(e) - e.count(e2)
print(ans)

### FIXED CODE ###

import collections

n = int(input())
v = list(map(int,input().split(" ")))
e,o = [],[]
e = v[::2]
o = v[1::2]

ec = collections.Counter(e).most_common(2)
oc = collections.Counter(o).most_common(2)

if ec[0][0] != oc[0][0]:
    print(n - ec[0][1] - oc[0][1])
else:
    if len(ec) == 1:
        print(n // 2)
    else:
        print(n - max(ec[0][1] + oc[1][1], ec[1][1] + oc[0][1]))
### BUGGY CODE ###

import math

N = int(input())
A = []

for i in range(N):
    s = input()
    if '.' in s:
        a,b = map(int,s.split('.'))
        if(int(b)==0):
            c = a
            d = 1
        else:
            c = a*pow(10,len(s)-s.find('.')-1)+b
            d = pow(10,len(s)-s.find('.')-1)
            g = math.gcd(c,d)
            c = c//g
            d = d//g
    else:
        c = int(s)
        d = 1
    e = 0
    f = 0
    while(c != 0 and c%2==0):
        e += 1
        c //= 2
    while(c != 0 and c%5==0):
        f += 1
        c //= 5
    while(d%2==0):
        e -= 1
        d //=2
    while(d%5==0):
        f -= 1
        d //=5
    A.append([e,f])

ans = 0

for i in range(len(A)-1):
    for j in range(i+1,len(A)):
        if (A[i][0]+A[j][0]>=0) and (A[i][1]+A[j][1]>=0):
            ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
A = []

for i in range(N):
    s = input()
    if '.' in s:
        a,b = map(int,s.split('.'))
        if(int(b)==0):
            c = a
            d = 1
        else:
            c = a*pow(10,len(s)-s.find('.')-1)+b
            d = pow(10,len(s)-s.find('.')-1)
    else:
        c = int(s)
        d = 1
    e = 0
    f = 0
    while(c != 0 and c%2==0):
        e += 1
        c //= 2
    while(c != 0 and c%5==0):
        f += 1
        c //= 5
    while(d%2==0):
        e -= 1
        d //=2
    while(d%5==0):
        f -= 1
        d //=5
    A.append([e,f])

tm = max(max([a[0] for a in A]), -1 * min([a[0] for a in A])) + 1
fm = max(max([a[1] for a in A]), -1 * min([a[1] for a in A])) + 1

B = [[0] * (tm * 2 ) for _ in range(fm * 2)]

for a in A:
    B[a[1]+fm][a[0]+tm] += 1

for i in range(fm*2):
    for j in range(tm*2):
        if(i>0):
            B[i][j] += B[i-1][j]
        if(j>0):
            B[i][j] += B[i][j-1]
        if(i>0 and j>0):
            B[i][j] -= B[i-1][j-1]

ans = 0
for a in A:
    i = -1 * a[1] + fm
    j = -1 * a[0] + tm
    ans += B[fm*2-1][tm*2-1] - B[fm*2-1][j-1] - B[i-1][tm*2-1] + B[i-1][j-1]
    if a[1]>=0 and a[0]>=0:
        ans -= 1

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

s = input()
K = int(input())
if K > 50:
    print(0)
    exit()
sub = {s[i:j] for i in range(len(s)+1) for j in range(i+1,len(s)+1)}
sub = sorted(sub)
print(sub[K-1])

### FIXED CODE ###

s = input()
K = int(input())
# if K > 50:
#     print(0)
#     exit()
sub = {s[i:j] for i in range(len(s)) for j in range(i+1,i+K+1)}
sub = sorted(sub)
print(sub[K-1])
### BUGGY CODE ###

S = list(input())
c = 0
while (1) :
    for i in range(len(S)-1) :
        if S[i] == 'B' and S[i+1] == 'W' :
            S[i] = 'W'
            S[i+1] = 'B'
            c += 1
            break
        elif i == len(S)-2 :
            print(c)
            exit()

### FIXED CODE ###

S = list(input())
c = 0
w = 0
for i in range(len(S)) :
    if S[i] == 'W' :
        c += i - w
        w += 1
print(c)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict
from queue import deque

def main():
  n = int(input())
  graph = defaultdict(list)
  
  def is_bt():
    def bfs():
      colors = [-1] * len(graph)
      dq = deque()
      dq.append(0)
      colors[0] = 0
      while dq:
        inode = dq.popleft()
        for ichild in graph[inode]:
          if colors[ichild] == -1:
            colors[ichild] = abs(colors[inode]-1)
            dq.append(ichild)
          else:
            if colors[ichild] == colors[inode]:
              return False
      return True
    return bfs()
  
  def wf(edges):
    dp = edges
    for k in range(len(graph)):
      for i in range(len(graph)):
        for j in range(len(graph)):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  
  edges = [[n+1] * n for _ in range(n)]  
  for i in range(n):
    for j, c in enumerate(input().strip()):
      if c == '1':
        graph[i].append(j)
        edges[i][j] = 1
    edges[i][i] = 0
  graph = dict(graph)
    
  if not is_bt():
    print(-1)
    return
  print(max([max(x) for x in wf(edges)]) + 1)
  
if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict
from queue import deque

def main():
  n = int(input())
  graph = defaultdict(list)
  
  def is_bt():
    def bfs():
      colors = [-1] * len(graph)
      dq = deque()
      dq.append(0)
      colors[0] = 0
      while dq:
        inode = dq.popleft()
        for ichild in graph[inode]:
          if colors[ichild] == -1:
            colors[ichild] = abs(colors[inode]-1)
            dq.append(ichild)
          else:
            if colors[ichild] == colors[inode]:
              return False
      return True
    return bfs()
  
  def wf(edges):
    dp = edges
    for k in range(len(graph)):
      for i in range(len(graph)):
        for j in range(len(graph)):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  
  edges = [[n+1] * n for _ in range(n)]  
  for i in range(n):
    for j, c in enumerate(input().strip()):
      if c == '1':
        graph[i].append(j)
        edges[i][j] = 1
    edges[i][i] = 0
  graph = dict(graph)
    
  if not is_bt():
    print(-1)
    return
  print(max([max(x) for x in wf(edges)]) + 1)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

x = input().split()

ab = ''.join(x)
ab = int(ab)
for i in range(0,int(ab/2)+1):
  for j in range(0,int(ab/2)+1):
    if(i*j == ab and i == j):
      print("Yes")
      #print(i,j)
      exit()
print("No")
                 

### FIXED CODE ###

import math as mt
x = input().split()

ab = ''.join(x)
ab = int(ab)
abr = mt.sqrt(ab)
for i in range(0,int(abr) + 1):
  for j in range(0,int(abr) + 1):
    if(i*j == ab and i == j):
      print("Yes")
      #print(i,j)
      exit()
print("No")
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
m = []
for _ in range(3):
    m.append(sorted(list(map(int, input().split())), reverse=True))

def sorted_sum(list_a, list_b):
    s = []
    for x in list_a:
        for y in list_b:
            s.append(x + y)
    return sorted(s, reverse=True)

ans = sorted_sum(sorted_sum(m[0], m[1]), m[2])
for i in range(0, k):
    print(ans[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
m = []
for _ in range(3):
    m.append(sorted(list(map(int, input().split())), reverse=True))

def sorted_sum(list_a, list_b, limit):
    s = []
    for x in list_a:
        for y in list_b:
            s.append(x + y)
    return sorted(s, reverse=True)[0:limit]


def consume_diff(s, a_val, list_b, b_index):
    diff = a_val - list_b[b_index]
    for i in range(b_index + 1, len(list_b)):
        if list_b[b_index] - list_b[i] > diff:
            break
        s.append(a_val + list_b[i])



ans = sorted_sum(sorted_sum(m[0], m[1], k), m[2], k)
for i in range(min([k, len(ans)])):
    print(ans[i])
### BUGGY CODE ###

#関数リスト
import sys
from bisect import bisect
input = sys.stdin.readline
def RD(): return input().rstrip()
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def main():
    N = I()
    A = LI()
    A.sort()
    B = LI()
    B.sort()
    B_len = len(B)
    C = LI()
    C.sort()
    C_len = len(C)
    result = 0
    A_init = A[0]
    for i in A:
        index = bisect(B,i)
        for j in range(index, B_len):
            if B[j] > i:
                result += C_len - bisect(C,B[j])
    print(result)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#関数リスト
import sys
import bisect
input = sys.stdin.readline
def RD(): return input().rstrip()
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def main():
    N = I()
    A = LI()
    A.sort()
    B = LI()
    B.sort()
    B_len = len(B)
    C = LI()
    C.sort()
    C_len = len(C)
    result = 0
    A_init = A[0]
    index = 0
    next_i = index
    
    for i in B:
        tempA = bisect.bisect_left(A,i) 
        tempC = C_len - bisect.bisect_right(C,i)
        result += tempA*tempC
    print(result)

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

def solver():
	N,W = map(int, input().split())
	item = []
	for i in range(N):
		item.append(list(map(int, input().split())))
	dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

	for i in range(0,N):
		for j in range(W+1):
			if(j < item[i][0]):
				dp[i+1][j] = dp[i][j]
			else:
				dp[i+1][j] = max(dp[i][j], dp[i][j-item[i][0]]+item[i][1])
	print(dp[N][W])

solver()

### FIXED CODE ###

def solver():
	N,W = map(int, input().split())
	item = []
	for i in range(N):
		item.append(list(map(int, input().split())))
	dp = [0 for _ in range(W+1)]
 
	for i in range(0,N):
		for j in range(W, item[i][0]-1, -1):
			dp[j] = max(dp[j], dp[j-item[i][0]]+item[i][1])
	print(dp[W])
 
solver()
### BUGGY CODE ###

from copy import deepcopy

N, M, Q = [int(elem) for elem in input().split(' ')]
lines = [[int(elem) for elem in input().split(' ')] for _ in range(M)]
queries = [[int(elem) for elem in input().split(' ')] for _ in range(Q)]


def cuml_1d(N, lines, queries):
    coords = [[0] * N for _ in range(N)]
    for l, r in lines:
        coords[l - 1][r - 1] += 1

    cuml_coords = deepcopy(coords)
    for l in range(N):
        for r in range(1, N):
            cuml_coords[l][r] = cuml_coords[l][r - 1] + coords[l][r]

    for query in queries:
        p, q = query[0] - 1, query[1] - 1
        num_lines = 0
        for l in range(p, max(q + 1, N)):
            if p == 0:
                num_lines += cuml_coords[l][q]
            else:
                num_lines += cuml_coords[l][q] - cuml_coords[l][p - 1]
        print(num_lines)

cuml_1d(N, lines, queries)


### FIXED CODE ###

from copy import deepcopy

N, M, Q = [int(elem) for elem in input().split(' ')]
lines = [[int(elem) for elem in input().split(' ')] for _ in range(M)]
queries = [[int(elem) for elem in input().split(' ')] for _ in range(Q)]


def cuml_1d(N, lines, queries):
    coords = [[0] * N for _ in range(N)]
    for l, r in lines:
        coords[l - 1][r - 1] += 1

    cuml_coords = deepcopy(coords)
    for l in range(N):
        for r in range(1, N):
            cuml_coords[l][r] = cuml_coords[l][r - 1] + coords[l][r]

    for query in queries:
        p, q = query[0] - 1, query[1] - 1
        num_lines = 0
        for l in range(p, max(q + 1, N)):
            if p == 0:
                num_lines += cuml_coords[l][q]
            else:
                num_lines += cuml_coords[l][q] - cuml_coords[l][p - 1]
        print(num_lines)

cuml_1d(N, lines, queries)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

h,w=map(int, input().split())
a = [input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
black = []
r_append = black.append
for i,row in enumerate(a):
    for j,c in enumerate(row):
        if c == '#':
            r_append((i,j))
            visited[i][j] = 0

queue = deque(black)

while queue:
    y,x = queue.popleft()
    dydx = [[1,0],[-1,0],[0,1],[0,-1]]
    for j,k in dydx:
        newy,newx = y+j,x+k 
        if newy < 0 or newy >= h:continue 
        if newx < 0 or newx >= w:continue 
        if visited[newy][newx] == -1:
            visited[newy][newx] = visited[y][x] + 1
            queue.append((newy,newx))

ans = 0
for row in visited:
    for j in row:
        ans = max(ans,j)

print(ans)

### FIXED CODE ###

from collections import deque

h,w=map(int, input().split())
a = [input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
black = []
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            black.append((i,j))
            visited[i][j] = 0

queue = deque(black)


while queue:
    y,x = queue.popleft()
    dydx = [[1,0],[-1,0],[0,1],[0,-1]]
    for j,k in dydx:
        newy,newx = y+j,x+k 
        if newy < 0 or newy >= h:continue 
        if newx < 0 or newx >= w:continue 
        if visited[newy][newx] == -1:
            visited[newy][newx] = visited[y][x] + 1
            queue.append((newy,newx))

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans,visited[i][j])

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

x, y, a, b, c = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse=True)
pp = p[:]
q = sorted(list(map(int, input().split())), reverse=True)
qq = q[:]
r = sorted(list(map(int, input().split())), reverse=True)
rr = r[:]
ans1 = 0
for _ in range(x):
    if len(p) > 0 and len(r) > 0:
        if p[0] >= r[0]:
            ans1 += p.pop(0)
        else:
            ans1 += r.pop(0)
    elif len(p) > 0:
        ans1 += p.pop(0)
    else:
        ans1 += r.pop(0)
for _ in range(y):
    if len(q) > 0 and len(r) > 0:
        if q[0] >= r[0]:
            ans1 += q.pop(0)
        else:
            ans1 += r.pop(0)
    elif len(q) > 0:
        ans1 += q.pop(0)
    else:
        ans1 += r.pop(0)

ans2 = 0
for _ in range(y):
    if len(qq) > 0 and len(rr) > 0:
        if qq[0] >= rr[0]:
            ans2 += qq.pop(0)
        else:
            ans2 += rr.pop(0)
    elif len(qq) > 0:
        ans2 += qq.pop(0)
    else:
        ans2 += rr.pop(0)
for _ in range(x):
    if len(pp) > 0 and len(rr) > 0:
        if pp[0] >= rr[0]:
            ans2 += pp.pop(0)
        else:
            ans2 += rr.pop(0)
    elif len(pp) > 0:
        ans2 += pp.pop(0)
    else:
        ans2 += rr.pop(0)
print(max(ans1, ans2))


### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse=True)
pp = p[:x]
q = sorted(list(map(int, input().split())), reverse=True)
qq = q[:y]
r = list(map(int, input().split()))

l = pp + qq + r
l.sort(reverse=True)
print(sum(l[:(x + y)]))
### BUGGY CODE ###

def main():
    S = input()
    n = len(S)
    i, j = 0, 4
    ans = 0
    while i <= n - 4:
        if eval(S[i:j] + ' % 2019 == 0'):
            ans += 1
        if j < n:
            j += 1
        else:
            i += 1
            j = i + 4
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter
def main():
    S = input()
    A = [0] * ((n := len(S)) + 1)
    A[1] = (a := int(S[-1])) % 2019
    for i in range(2, n + 1):
        a += pow(10, i - 1, 2019) * int(S[-i])
        A[i] = a % 2019
    c = Counter(A)
    ans = 0
    for v in c.values():
        ans += v * (v - 1) // 2
    print(ans)

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

import sys
input = sys.stdin.readline

INF=float('inf')
n, k = map(int,input().split())
h = list(map(int, input().split()))
dp=[0]+[INF]*(n-1)
for i in range(1,n):
    for j in range(1,min(i+1,k+1)):
        dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline

INF=float('inf')
n, k = map(int,input().split())
h = list(map(int, input().split()))
dp=[0]+[INF]*(n-1)
for i in range(1,n):
    for j in range(1,min(i+1,k+1)):
        dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[-1])
### BUGGY CODE ###

s1 = list(input())
s2 = list(input())
n = len(s1)
m = len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1, m+1):
        if s1[i-1] == s2[j-1]:
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
res = ''
i, j = n, m
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res = s1[i-1] + res
        i -= 1
        j -= 1
print(res)

### FIXED CODE ###

s1 = list(input())
s2 = list(input())
n = len(s1)
m = len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1, m+1):
        if s1[i-1] == s2[j-1]:
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
res = []
i, j = n, m
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res.append(s1[i-1])
        i -= 1
        j -= 1
print(''.join(res[::-1]))
### BUGGY CODE ###

S = input()
K = int(input())
store = []
for i in range(len(S)):
  N = i+1
  while N <= len(S):
    store.append(S[i:N])
    N += 1
store_set = set(store)
store_list = list(store_set)
store_list.sort()
print(store_list[K-1])


### FIXED CODE ###

S = input()
K = int(input())
store = []
for i in range(len(S)):
  N = i+1
  while N <= i + 5:
    store.append(S[i:N])
    N += 1
store_set = set(store)
store_list = list(store_set)

List = [ x for x in store_list  if len(x) <= K ]
List.sort()
print(List[K-1])