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

from collections import deque
import copy
H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
S = []
for i in range(H):
  for j in range(W):
    if maze[i][j] == ".":
      maze[i][j] = float("inf")
      S.append([i, j])
    else:
      maze[i][j] = -1
def bfs(H, W, maze, S):
  ans = 0
  for sy, sx in S:
    maze1 = copy.deepcopy(maze)
    maze1[sy][sx] = 0
    q = deque()
    q.append([sy,sx])
    while len(q)>0:
      y, x = q.popleft()
      for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
        nexty = y+i
        nextx = x+j
        if nexty < 0 or nexty>=H or nextx < 0 or nextx>=W:
          continue
        dist = maze1[nexty][nextx]
        if maze1[nexty][nextx] != -1:
          if dist > maze1[y][x]:
            maze1[nexty][nextx] = maze1[y][x] + 1
            q.append([nexty, nextx])
        ans = max(ans, maze1[nexty][nextx])
  print(ans)
bfs(H, W, maze, S)

### FIXED CODE ###

from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
            else:
                maze[y][x]=-1
    l = []
    ans = 0
    for i in range(len(S)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!=-1:
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                que.append([nexty,nextx])
            ans = max(ans, maze1[nexty][nextx])
    print(ans)
bfs()
### BUGGY CODE ###

def uauau():
    N = int(input())
    aA=sorted(set(int(_) for _ in input().split()))
    N = len(aA)
    def ggg(i,j):
        i %= j
        if i == 0:
            return j
        else:
            return ggg(j,i)

    if len(aA) == 1:
        print(aA[0])
    else:
        iMin = aA[0]
        iMax = aA[-1]
        if iMin  == 1:
            print(1)
        else:
            iMt = max(i % iMin for i in aA)
            if iMt == 0:
                print(iMin)
                exit()
            elif iMt  == 1:
                print (1)
            else:
                iM = iMax
                for i in range(N):
                    iA = aA[i]
                    for j in range(i+1,N):
                        if aA[j] % iA != 0:
                            iMt = ggg(aA[j],iA)
                            if iMt < iM:
                                iM = iMt
                    if iM == 1:
                        print(1)
                        exit()
                print(iM)
uauau()


### FIXED CODE ###

#gcdか....
def fgcd(a,b):
    while b:
        a,b = b,a%b
    return a

N = int(input())
aA = sorted(set(int(_) for _ in input().split()))
b = aA[0]
for a in aA[1:]:
    b = fgcd(a,b)
print(b)
### BUGGY CODE ###

s = input()
q = int(input())

cnt = 0
llst = []
rlst = []
for i in range(q):
  line = input()
  if line == '1':
    cnt += 1
  else:
    elems = line.split()
    if cnt % 2 == 0:
      # 指示通り追加
      if elems[1] == '1':
        llst = [elems[2]] + llst
      else:
        rlst.append(elems[2])
    else:
      # 指示の向きと逆に追加
      if elems[1] == '1':
        rlst.append(elems[2])
      else:
        llst = [elems[2]] + llst
        
if cnt % 2 == 0:
  res = ''.join(llst) + s + ''.join(rlst)
  print(res)
else:
  res = ''.join(llst) + s + ''.join(rlst)
  print(''.join(list(reversed(res))))

### FIXED CODE ###

s = input()
q = int(input())

cnt = 0
llst = []
rlst = []
for i in range(q):
  line = input()
  if line == '1':
    cnt += 1
  else:
    elems = line.split()
    if cnt % 2 == 0:
      # 指示通り追加
      if elems[1] == '1':
        llst.append(elems[2])
      else:
        rlst.append(elems[2])
    else:
      # 指示の向きと逆に追加
      if elems[1] == '1':
        rlst.append(elems[2])
      else:
        llst.append(elems[2])
        
if cnt % 2 == 0:
  res = ''.join(llst[::-1]) + s + ''.join(rlst)
  print(res)
else:
  res = ''.join(llst[::-1]) + s + ''.join(rlst)
  print(res[::-1])
### BUGGY CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
R = 1000000007
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

def dfs(x,y):
    if x == n:
        return 1
    if dp[y] > -1:
        return dp[y]
    sum = 0
    for j in range(n):
        if a[x][j] == 1 and (y>>j)%2 == 0:
            sum = (sum + dfs(x+1, y|(1<<j))) % R
    dp[y] = sum
    return sum

n = inn()
a = [ 0 for i in range(n) ]
for i in range(n):
    a[i] = inl()
dp = [-1] * (2**n)
print(dfs(0,0))


### FIXED CODE ###

inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
R = 1000000007

def dfs(x,y):
    if x == n:
        return 1
    if dp[y] > -1:
        return dp[y]
    sum = 0
    for j in range(n):
        b = 1 << j
        if a[x][j] == 1 and (y&b) == 0:
            sum += dfs(x+1, y|b)
            if sum > R:
                sum -= R
    dp[y] = sum
    return sum

n = inn()
a = [ 0 for i in range(n) ]
for i in range(n):
    a[i] = inl()
dp = [-1] * (2**n)
print(dfs(0,0))
### BUGGY CODE ###

CONST = 100000

class EndLoop(Exception):
    pass

def solve():
    N = int(input())
    try:
        for h in range(1, CONST):
            for n in range(1, CONST):
                for w in range(1, CONST):
                    if (4 * h * n * w) % (n * w + h * w + h * n):
                        continue

                    if (4 * h * n * w) / (n * w + h * w + h * n) == N:
                        print(h, n, w)
                        raise EndLoop

    except EndLoop:
        pass


solve()

### FIXED CODE ###

class EndLoop(Exception):
    pass


def solve():
    N = int(input())
    try:
        for h in range(1, 3501):
            for n in range(1, 3501):
                if 4 * h * n - n * N - h * N > 0:
                    if (h * n * N) % (4 * h * n - n * N - h * N) == 0:
                        w = int((h * n * N) / (4 * h * n - n * N - h * N))
                        print(h, n, int(w))
                        raise EndLoop
    except:
        pass


solve()
### BUGGY CODE ###

X,Y = map(int,input().split())
dp = [[0 for i in range(Y+10)] for _ in range(X+10)]
dp[2][1] = 1
dp[1][2] = 1

for i in range(2,X+1):
    for j in range(max(2,i//2),min(Y+1,i*2+1)):
        if (i+j) % 3 == 0:
            dp[i][j] = (dp[i-2][j-1] + dp[i-1][j-2]) % (10**9+7)

print(dp[X][Y])

### FIXED CODE ###

X,Y = map(int,input().split())

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def combi(n,r,mod=10**9+7):
    fac = [0]*(n+1)
    fac[0] = 1
    fac[1] = 1
    for i in range(2,n+1):
        fac[i] = fac[i-1] * i % mod
    return( ( fac[n] * modinv(fac[r]) )%mod * modinv(fac[n-r]) % mod)

if (X+Y) % 3 != 0 or X > 2*Y or Y > 2*X:
    print(0)
else:
    n = X - (X + Y)//3
    m = (X + Y)//3 - n
    print(combi(n+m,m))
### BUGGY CODE ###

import sys
from bisect import bisect_left, bisect, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    b = sorted(list(map(int, input().split())))
    c = sorted(list(map(int, input().split())))

    cnt = 0
    for x in a:
        i = bisect(b, x)
        for y in b[i:]:
            j = bisect(c, y)
            cnt += len(c[j:])

    print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    b = sorted(list(map(int, input().split())))
    c = sorted(list(map(int, input().split())))

    cnt = 0
    for x in b:
        cnt += bisect_left(a, x)*(n-bisect_right(c, x))
    print(cnt)


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

n, m = map(int, input().split())
s = input()
t = input()

def gcd(a, b):
    if b == 0:
        return abs(a)
    else:
        return gcd(b, a % b)


l = n * m // gcd(n, m)

ok = True
nn = l // n
mm = l // m

for i in range(l):
    if i % nn == 0 and i % mm == 0:
        if i // nn > n:
            continue
        if i // mm > m:
            continue
        if s[i // nn] != t[i // mm]:
            ok = False

print(l if ok else -1)


### FIXED CODE ###

n, m = map(int, input().split())
s = input()
t = input()

def gcd(a, b):
    if b == 0:
        return abs(a)
    else:
        return gcd(b, a % b)


l = n * m // gcd(n, m)

ok = True
nn = l // n
mm = l // m

i = 0
j = 0

while True:
    if i < j:
        i += nn
    elif j < i:
        j += mm
    else:
        if i // nn < n and j // mm < m:
            if s[i // nn] != t[j // mm]:
                ok = False
        else:
            break
        i += nn
    #print(i, j, nn, mm)

print(l if ok else -1)
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline
def change(after,index,li):
    before = li[index]
    for i in range(len(li)):
        if li[i]==before:
            li[i]=after
def main():
    n,k,l = map(int,input().split())
    road=[0 for _ in range(n)]
    train=[0 for _ in range(n)]
    r=t=1
    for _ in range(k):
        p,q = map(int,input().split())
        if road[p-1]==0 and road[q-1]==0:
            road[p-1]=road[q-1]=r
            r+=1
        elif road[p-1]!=0 and road[q-1]==0:
            road[q-1]=road[p-1]
        elif road[p-1]==0 and road[q-1]!=0:
            road[p-1]=road[q-1]
        else:
            change(road[p-1],q-1,road)
    for _ in range(l):
        p,q = map(int,input().split())
        if train[p-1]==0 and train[q-1]==0:
            train[p-1]=train[q-1]=t
            t+=1
        elif train[p-1]!=0 and train[q-1]==0:
            train[q-1]=train[p-1]
        elif train[p-1]==0 and train[q-1]!=0:
            train[p-1]=train[q-1]
        else:
            change(train[p-1],q-1,train)
    for i in range(n):
        ans=1
        if train[i]!=0 or road[i]!=0:
            for j in range(n):
                if i!=j and train[i]!=0 and train[i]==train[j] and road[i]!=0 and  road[i]==road[j]:
                    ans+=1
        print(ans)
main()

### FIXED CODE ###

from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue,copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inpln(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])

def find(x): # 木の根を求める
    if par[x]==x:
        return x
    else:
        return find(par[x])

def unite(x,y): # xとyの属する集合を併合
    x=find(x)
    y=find(y)
    if x==y:return
    if rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1

def same(x,y): # xとyが同じ集合に属するか判定
    return find(x)==find(y)
 
def main():
    n,k,l = inpm()
 
    global par,rank
    par  = [i for i in range(2*n)]
    rank = [-1 for _ in range(2*n)] 
    for _ in range(k):
        p,q = inpm()
        p-=1
        q-=1
        unite(p,q)
    for _ in range(l):
        r,s = inpm()
        r-=1
        s-=1
        unite(r+n,s+n)

    root_s=defaultdict(int)
    root=[]
    for i in range(n):
        root.append(str(find(i))+' '+str(find(i+n)))
        root_s[root[i]]+=1
    
    ans=[0 for _ in range(n)]
    for i in range(n):
        ans[i] = root_s[root[i]]
    print(*ans) 


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

# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections
import itertools
mod = 10 ** 9 + 7
N = int(input())
L = list(map(int, input().split()))
count = 0
for a, b, c in itertools.combinations(L, 3):
    if ((a < b + c) and (b < a + c) and (c < a + b)):
        count += 1
print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections
import itertools
import bisect
mod = 10 ** 9 + 7
N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
count = 0
for i in range(len(L)):
    for j in range(i+1, len(L)):
        a = L[i]
        b = L[j]
        idx = insert_index = bisect.bisect_left(L, a+b)
        count += max(0, idx-j-1)


print(count)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
b=a[0];c=1
while not (b==1 or b==2):
  c+=1
  b=a[b-1]
if b==1:print(-1)
else:print(c)

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
b=a[0];c=1
while b!=2 and c<=n:
  b=a[b-1]
  c+=1
if b==2:print(c)
else:print(-1)
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    while i < N :
        if None not in ANS[i:i+5] :
            i += 5
            continue
        ANS[i] = min(Whole[i+1-L:i+1])
        i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.9997
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
def gcd(x,y):
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
for i in range(n):
    ans+=l//a[i]
print(ans%mod)
 

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
import fractions
mod=10**9+7
ans=0
l=a[0]
for i in range(1,n):
    l=l*a[i]//fractions.gcd(l,a[i])
for i in range(n):
    ans+=l//a[i]
print(ans%mod)
### BUGGY CODE ###

import heapq
N,M = (int(x) for x in input().split())
citiespref = []
pref = [[] for _ in range(N)]
ans = [0] * M
prefnumber = 0
for i in range(M):
    P,Y = (int(x) for x in input().split())
    citiespref.append(P)
    pref[P-1].append((Y,i))
for p in pref:
    prefnumber += 1
    count = 1
    while p:
        heapq.heapify(p)
        temp = heapq.heappop(p)
        ans[temp[1]] = str(prefnumber).zfill(6) + str(count).zfill(6)
        count += 1
for a in ans:
    print(a)

### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq
N,M = (int(x) for x in input().split())
pref = [[] for _ in range(N)]
ans = [0] * M
prefnumber = 0
for i in range(M):
    P,Y = (int(x) for x in input().split())
    pref[P-1].append((Y,i))
for p in pref:
    prefnumber += 1
    count = 1
    if p:
        heapq.heapify(p)
        while p:
            temp = heapq.heappop(p)
            ans[temp[1]] = ''.join([str(prefnumber).zfill(6),str(count).zfill(6)])
            count += 1
print('\n'.join(ans))
### BUGGY CODE ###

n, m = map(int, input().split())
graph = [tuple(map(int, input().split())) for _ in range(m)]

def shortest_path(s):
    MIN = -1 * 10 ** 12
    d = [MIN] * (n + 1)
    d[s] = 0
    update = True
    cnt = 1
    tmp = MIN
    while update:
        update = False
        for a, b, c in graph:
            if d[a] != MIN and d[b] < d[a] + c:
                d[b] = d[a] + c
                update = True
        if cnt == m: tmp = d[n]
        if update and cnt == 2 * m and d[n] > tmp: return 'inf'
        cnt += 1
    return d[n]

print(shortest_path(1))

### FIXED CODE ###

n, m = map(int, input().split())
graph = [tuple(map(int, input().split())) for _ in range(m)]

def shortest_path(s):
    MIN = -1 * 10 ** 12
    d = [MIN] * (n + 1)
    d[s] = 0
    update = True
    cnt = 1
    tmp = MIN
    while update:
        update = False
        for a, b, c in graph:
            if d[a] != MIN and d[b] < d[a] + c:
                d[b] = d[a] + c
                update = True
        if cnt == m: tmp = d[n]
        if update and cnt == 2 * m and d[n] > tmp: return 'inf'
        if cnt == 2 * m: update = False
        cnt += 1
    return d[n]

print(shortest_path(1))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

from collections import deque

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

edges = [None] * M
for i in range(M):
    l, r, d = map(int, input().split())
    edges[i] = (l-1, r-1, d)

# 訪問済メモ
visited = [0] * N

def bfs(start):
    # この開始位置を基準とした相対位置を記録する
    pos = {start: 0}
    que = deque()
    que.append(start)
    visited[start] = 1
    while len(que) != 0:
        cur = que.popleft()
        # 辺のループ
        for l, r, d in edges:
            # 左から見た右側を確認
            if l == cur:
                # 訪問済なら矛盾がないか検証する
                if visited[r]:
                    if pos[r] - pos[l] != d:
                        print('No')
                        exit()
                # 未訪問なら今回の情報を記録する
                else:
                    visited[r] = 1
                    pos[r] = pos[l] + d
                    # 次回以降、開始位置として使うのでキューに詰める
                    que.append(r)
            # 右から見た左側を確認
            elif r == cur:
                if visited[l]:
                    if pos[r] - pos[l] != d:
                        print('No')
                        exit()
                else:
                    visited[l] = 1
                    pos[l] = pos[r] - d
                    que.append(l)

for i in range(N):
    # 訪問済(確認済)でなければ走破しに行く
    if not visited[i]:
        bfs(i)
# 最後まで矛盾がなければOK
print('Yes')


### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
参考：http://hamko.hatenadiary.jp/entry/2018/01/30/210057
　　　http://at274.hatenablog.com/entry/2018/02/03/140504
・重み付きUnion-Find木
"""

class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = - w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

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

wuf = WeightedUnionFind(N)
for i in range(M):
    x, y, w = map(int, input().split())
    # 同じ集合に属する場合は
    if wuf.same(x, y):
        # 記録された距離と今回の情報に矛盾がないか確認
        if wuf.diff(x, y) != w:
            print('No')
            exit()
    wuf.union(x, y, w)
# 全部無矛盾で木が構築できればOK
print('Yes')
### BUGGY CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]
def sol(i, cur):
    if i == -1:
        return cur
    else:
        tmp1 = sol(i-1, cur+a[i])
        tmp1 = tmp1 if tmp1 % 10  else 0
        tmp2 = sol(i-1, cur)
        tmp2 = tmp2 if tmp2 % 10 else 0
        return max(tmp1, tmp2)
print(sol(N-1, 0))

### FIXED CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]
ans = sum(a)
if ans % 10 == 0:
    if all([i % 10 == 0 for i in a]):
        print(0)
    else:
        ans -= min([i for i in a if i % 10 != 0])
        print(ans)
else:
    print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
DP=[0]*N
DP[0]=0
i=1
while i<N:
  min_dist=float('inf')
  j=1
  while j<=K and j<=i:
    min_dist=min(min_dist,abs(h[i]-h[i-j])+DP[i-j])
    j+=1
  DP[i]=min_dist
  i+=1
print(DP[-1])




### FIXED CODE ###

def main():
  #import sys
  #input = sys.stdin.readline
  N,K=map(int,input().split())
  h=list(map(int,input().split()))
  DP=[0]*N
  DP[0]=0
  for i in range(1,N):
  #j=1
  #while j<=K and j<=i:
  #  DP[i]=min(DP[i],abs(h[i]-h[i-j])+DP[i-j])
  #for j in range(max(0, i-K),i):
    #DP[i]=min(DP[i],abs(h[i]-h[j])+DP[j])
    r=max(0, i-K)
    DP[i]=min([abs(h[i]-h[j])+DP[j] for j in range(r,i)])
  print(DP[-1])
if __name__ == '__main__':
  main()
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = map(int, input().split())
b = list(map(int, input().split()))
c = map(int, input().split())
d = sorted((ai + bi for ai in a for bi in b), reverse=True)[:k]
e = sorted((ci + di for ci in c for di in d), reverse=True)
i = 0
while i != k:
    print(e[i])
    i += 1


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = map(int, input().split())
b = list(map(int, input().split()))
c = map(int, input().split())
d = sorted((ai + bi for ai in a for bi in b), reverse=True)[:k]
e = sorted((ci + di for ci in c for di in d), reverse=True)[:k]
print(*e)
### BUGGY CODE ###

import fractions
from functools import reduce

def lcm_base(x, y):
  return (x*y) // fractions.gcd(x,y)
def lcm_list(numbers):
  return reduce(lcm_base,numbers,1)

N=int(input())
alist=list(map(int,input().split()))

if N==1:
  print(1)
else:
  alist.sort()
  lcm_alist=lcm_list(alist)
  
  answer=0
  last_a=-1
  last_b=-1
  for a in alist:
    b=last_b
    if a!=last_a:
      b=lcm_alist//a
      last_b=b

    answer=(answer+b)%(10**9+7)
    
  #print(blist)
  print(answer)

### FIXED CODE ###

import fractions
import sys
from functools import reduce

def lcm_base(x, y):
  return (x*y) // fractions.gcd(x, y)
def lcm_list(numbers):
  return reduce(lcm_base, numbers, 1)

N=int(input())
alist=list(map(int,input().split()))

if N==1:
  print(1)
else:
  lcm_alist=lcm_list(alist)
  #print(lcm_alist)
  
  allsum=0
  for i in range(N):
    allsum+=lcm_alist//alist[i]
    
  #print(blist)
  print(allsum%(10**9+7))
### BUGGY CODE ###

import bisect
N = int(input())
L = list(map(int,input().split()))
L = sorted(L)
res = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        tgt = L[i]+L[j] - 0.1
        res += bisect.bisect_right(L[j+1:], tgt)
print(res)


### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int,input().split()))
L = sorted(L)
res = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        tgt = L[i]+L[j]
        res += bisect.bisect_left(L, tgt)-(j+1)
print(res)