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

import queue
import sys

input = sys.stdin.readline


class Solution:
    def main(self):
        H, W = map(int, input().split())
        S = [list(input().rstrip()) for _ in range(H)]

        for i in range(H):
            S[i] = ["#"] + S[i] + ["#"]
        S = [["#"] * (W + 2)] + S + [["#"] * (W + 2)]

        ans = 0
        for i in range(1, H + 1):
            for j in range(1, W + 1):
                if S[i][j] == "#":
                    continue
                for n in range(1, H + 1):
                    for m in range(1, W + 1):
                        if S[n][m] == "#":
                            continue
                        v = self.min_move(S, (i, j), (n, m))
                        ans = max(ans, v)
        print(ans)

    def min_move(self, map, start, goal):
        moving_range = ((1, 0), (-1, 0), (0, 1), (0, -1))

        q = queue.Queue()
        q.put((start, 0))

        while q:
            pos, cnt = q.get()
            if pos == goal:
                return cnt

            for move in moving_range:
                i, j = pos[0] + move[0], pos[1] + move[1]
                if map[i][j] == ".":
                    q.put(((i, j), cnt + 1))


# Run main
if __name__ == '__main__':
    Solution().main()


### FIXED CODE ###

import queue
import sys

input = sys.stdin.readline


class Solution:
    def main(self):
        H, W = map(int, input().split())
        S = [list(input().rstrip()) for _ in range(H)]

        for i in range(H):
            S[i] = ["#"] + S[i] + ["#"]
        S = [["#"] * (W + 2)] + S + [["#"] * (W + 2)]

        ans = 0
        for i in range(1, H + 1):
            for j in range(1, W + 1):
                if S[i][j] == "#":
                    continue
                v = self.min_move(S, (i, j))
                ans = max(ans, v)
        print(ans)

    def min_move(self, map, start):
        moving_range = ((1, 0), (-1, 0), (0, 1), (0, -1))

        q = queue.Queue()
        q.put((start, 0))

        already = {start}
        ret = 0
        while not q.empty():
            pos, cnt = q.get()
            ret = max(ret, cnt)
            for move in moving_range:
                i, j = pos[0] + move[0], pos[1] + move[1]
                if (i, j) not in already and map[i][j] == ".":
                    q.put(((i, j), cnt + 1))
                    already.add((i, j))

        return ret


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

K = int(input())
if K % 2 == 0:
    print(-1)
    exit()
start = j = 7 % K
count = 1
while j != 0:
    j = 10 * j + 7
    j = j % K
    count += 1
    if j == start:
        print(-1)
        exit()
print(count)

### FIXED CODE ###

K = int(input())
if K % 2 == 0 or K % 5 == 0:
    print(-1)
    exit()

start = j = 7 % K
count = 1

#無限ループ
while True:
    #0の時
    if j == 0:
        print(count)
        exit()
        
    j = 10 * j + 7
    j = j % K
    count += 1
    
    #同じ数のループしているかチェック
    if j == start:
        print(-1)
        exit()
### BUGGY CODE ###

A,B,Q=map(int,input().split())
inf=1e50
s=[int(input()) for _ in range(A)]
s=[-inf]+s+[inf]
t=[int(input()) for _ in range(B)]
t=[-inf]+t+[inf]

from bisect import bisect

for _ in range(Q):
    x=int(input())
    i=bisect(s,x)
    j=bisect(t,x)
    
    sL=x-s[i-1]
    sR=s[i]-x
    
    tL=x-t[j-1]
    tR=t[j]-x
    print(min(max(sR,tR),max(sL,tL),sR+tL+min(sR,tL),sL+tR+min(sL,tR)))




### FIXED CODE ###

A,B,Q=map(int,input().split())
inf=1e50
s=[-inf]
for _ in range(A):
    s.append(int(input()))
s.append(inf)

t=[-inf]
for _ in range(B):
    t.append(int(input()))
t.append(inf)
from bisect import bisect

for _ in range(Q):
    x=int(input())
    i=bisect(s,x)
    j=bisect(t,x)
    
    sL=x-s[i-1]
    sR=s[i]-x
    
    tL=x-t[j-1]
    tR=t[j]-x
    print(min(max(sR,tR),max(sL,tL),sR+tL+min(sR,tL),sL+tR+min(sL,tR)))
### BUGGY CODE ###

class SegmentTree:
  def __init__(self, size, default, op = min):
    self.size = 2**size.bit_length()
    self.dat = [default]*(self.size*2)
    self.op = op

  def update(self, i, x):
    i += self.size
    self.dat[i] = x
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

  def add(self, i, x):
    i += self.size
    self.dat[i] = self.op(self.dat[i], x)
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i], x)

  def get(self, a, b = None):
    if b is None:
      b = a + 1
    l, r = a + self.size, b + self.size
    res = None
    while l < r:
      if l & 1:
        if res is None:
          res = self.dat[l]
        else:
          res = self.op(res, self.dat[l])
        l += 1

      if r & 1:
        r -= 1
        if res is None:
          res = self.dat[r]
        else:
          res = self.op(res, self.dat[r])
      l >>= 1
      r >>= 1
    return res

N,M = map(int,input().split())
LRC = [list(map(int,input().split())) for _ in range(M)]
LRC.sort(key=lambda x:(x[0],x[1]))
#print(LRC)

INF = 10**18
dp = SegmentTree(N,INF,min)
dp.update(0,0)
#print(dp.get(0,1))

for l,r,c in LRC:
  p = dp.get(l-1,r-1)+c
  for i in range(l,r):
    dp.update(i,min(p,dp.get(i)))
print(dp.get(N-1) if dp.get(N-1) != INF else -1)


### FIXED CODE ###

class SegmentTree:
  def __init__(self, size, default, op = min):
    self.size = 2**size.bit_length()
    self.dat = [default]*(self.size*2)
    self.op = op

  def update(self, i, x):
    i += self.size
    self.dat[i] = x
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

  def add(self, i, x):
    i += self.size
    self.dat[i] = self.op(self.dat[i], x)
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i], x)

  def get(self, a, b = None):
    if b is None:
      b = a + 1
    l, r = a + self.size, b + self.size
    res = None
    while l < r:
      if l & 1:
        if res is None:
          res = self.dat[l]
        else:
          res = self.op(res, self.dat[l])
        l += 1

      if r & 1:
        r -= 1
        if res is None:
          res = self.dat[r]
        else:
          res = self.op(res, self.dat[r])
      l >>= 1
      r >>= 1
    return res

N,M = map(int,input().split())
LRC = [list(map(int,input().split())) for _ in range(M)]
LRC.sort(key=lambda x:(x[0],x[1]))
#print(LRC)

INF = 10**18
dp = SegmentTree(N,INF,min)
dp.update(0,0)
#print(dp.get(0,1))

for l,r,c in LRC:
  p = dp.get(l-1,r-1)+c
  # cf.https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/1109_nikkei2019-2-qual
  #for i in range(l,r):
  #  if p < dp.get(i):
  #    dp.update(i,p)
  if p < dp.get(r-1):
    dp.update(r-1,p)
print(dp.get(N-1) if dp.get(N-1) != INF else -1)
### BUGGY CODE ###

K,S=map(int, input().split())
count = 0
for x in range(K+1):
  for y in range(K+1):
    for z in range(K+1):
      if x+y+z == S:
        count = count + 1
print(count)

### FIXED CODE ###

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

def go():
    n,q=map(int,input().split())
    mas=[1 for i in range(n)]
    s=list(input())
    td=[list(map(str,input().split()))for i in range(q)]
    for t,d in td:
        indexall=[i for i, x in enumerate(s) if x==t]
        for i in indexall:
            if mas[i]>0:
                memo=mas[i]
                mas[i]=0
                if d=='L':
                    if i-1>=0:
                        mas[i-1]+=memo
                else:
                    if i+1<=n-1:
                        mas[i+1]+=memo

    return sum(mas)

print(go())

### FIXED CODE ###

def nibu():
    n,q=map(int,input().split())
    s=[0]+list(input())+[0]
    td=[input().split()for i in range(q)][::-1]

    L=0
    R=n+1

    for t,d in td:
        if t==s[L+1] and d=='L':
            L+=1
        elif t==s[L] and d=='R':
            L-=1
        
        if t==s[R-1] and d=='R':
            R-=1
        elif t==s[R] and d=='L':
            R+=1

    return max(0,R-L-1)

print(nibu())
### BUGGY CODE ###

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

### FIXED CODE ###

def test():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [float('inf')]*N
    dp[0] = 0
 
    for i in range(1, N):
        dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i-K, 0), i))
 
    print(dp[-1])
 
if __name__ == '__main__':
    test()
### BUGGY CODE ###

x, y, z, k = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list((map(int,input().split())))
D = []
E = []
for i in range(x):
  for j in range(y):
    D.append(A[i]+B[j])
D = sorted(D, reverse=True)
for j in range(len(D)):
  for i in range(z):
    E.append(C[i]+D[j])
E = sorted(E, reverse=True)
for i in range(k):
  print(E[i])

### FIXED CODE ###

x, y, z, k = [int(n) for n in input().split()]
va = sorted([int(n) for n in input().split()], reverse=True)
vb = sorted([int(n) for n in input().split()], reverse=True)
xy = min(x*y, k)
vab = (sorted([a + b for a in va for b in vb], reverse=True))[:xy]
vc = sorted([int(n) for n in input().split()], reverse=True)
xyz = min(x*y*z, k)
print(*((sorted([ab + c for ab in vab for c in vc], reverse=True))[:xyz]), sep="\n")
### BUGGY CODE ###

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

table = {}
init_table = {}
move = {}

for i in range(N):
    if A[i] in table:
        move[table[A[i]]], move[i] = i+1, init_table[A[i]]+1
    else:
        if A[i] not in init_table:
            init_table[A[i]] = i
    table[A[i]] = i

T = K
next_idx = 0
remain = {}
for i in range(1, K+1):
    idx = next_idx
    while idx in move and idx < move[idx]:
        idx = move[idx]
    remain[i] = idx
    if idx in move:
        next_idx = move[idx]
    else:
        next_idx += 1
    if(idx == N and i != K):
        T = K % i
        break

if(T == 0):
    print()
    exit()
idx = remain[T]
ret = []
while idx < len(A):
    while idx in move and idx < move[idx]:
        idx = move[idx]
    if(idx >= len(A)):
        break
    ret.append(A[idx])
    idx += 1

print(*ret)



### FIXED CODE ###

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

if n == 1:
    if k % 2:
        print(*arr)
    else:
        print(*[])
    exit()

table = {}
original_table = {}
move = {}

for i, a in enumerate(arr):
    if a not in table:
        table[a] = i
        original_table[a] = i
    else:
        move[table[a]], move[i] = i + 1, original_table[a] + 1
        table[a] = i

res = {}
idx = 0

for i in range(1, k + 1):
    while idx in move and move[idx] > idx:
        idx = move[idx]

    res[i] = idx
    if idx == len(arr):
        k %= len(res)
        if not k:
            k = len(res)
        break

    if idx in move:
        idx = move[idx]
    else:
        idx += 1

idx = res[k]
response = []

while idx < len(arr):
    while idx in move and move[idx] > idx:
        idx = move[idx]
    if idx < len(arr):
        response.append(arr[idx])
    idx += 1

print(*response)
### BUGGY CODE ###

from math import gcd
from itertools import product
from functools import reduce

l1 = [i for i in range(1, int(input()) + 1)]
print(sum(reduce(gcd, l) for l in product(l1, repeat=3)))


### FIXED CODE ###

from math import gcd
from itertools import product
from functools import reduce

l1 = [i for i in range(1, int(input()) + 1)]
print(sum(reduce(gcd, l) for l in product(l1, repeat=3)))
### BUGGY CODE ###

n = int(input())
p = [int(x) for x in input().split()]
cnt = n
for i in range(n):
    for j in range(i):
        if p[i] <= p[j]:
            continue
        cnt -= 1
        break
print(cnt)

### FIXED CODE ###

n = int(input())
p = [int(x) for x in input().split()]
cnt = 0
tmp = float('inf')
for i in range(n):
    if p[i] < tmp:
        tmp = p[i]
        cnt += 1
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    
    out = 1
    for n in A:
        out = n * out
    
    if out > 1000000000000000000:
        print(-1)
    else:
        print(out)



main()

### FIXED CODE ###

#!/usr/bin/env python3

def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    if 0 in A:
        print(0)
    else:
        out = 1
        for n in A:
            out = n * out
            if out > 1000000000000000000:
                break
            else:
                continue
    
        if out > 1000000000000000000:
            print(-1)
        else:
            print(out)


main()
### BUGGY CODE ###

import fractions
a,b = map(int, input().split())
g = fractions.gcd(a,b)
l = []

for i in range(2, g+1):
  if g%i == 0 and min(a,b)%i == 0:
    for j in range(2, i):
      if i%j == 0:
        break
    else:
      l.append(i)

print(len(l)+1)

### FIXED CODE ###

import fractions
import math
a,b = map(int, input().split())
g = fractions.gcd(a,b)
ans = 1

for i in range(2, int(math.sqrt(g))+1):
  if g%i == 0:
    ans += 1
    while True:
      g //= i
      if g%i != 0:
        break
if (g != 1):
  ans += 1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n, m = lmi()
a = [int(input()) for i in range(m)]

l = [0] * (n+1)
l[0] = 1
for i in range(n+1):
     if i not in a:

         if i == 1:
            l[i] = 1
         elif i >= 2:
            l[i] = l[i-1] + l[i-2]


#print(l)
print(l[n]%1000000007)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n, m = lmi()

l = [0] * (n+1)
l[0] = 1

a = 0
if m != 0:
    a = int(input())
k = 1
for i in range(n+1):

    if i != a:
        if i == 1:
            l[i] = 1
        elif i >= 2:
            l[i] = l[i-1] + l[i-2]
            l[i] %= 1000000007
    else:
        k += 1
        if k <= m:
            a = int(input())



#print(l)
print(l[n] % 1000000007)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    H, W, D = LI()
    mod_array = [[0 for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(H):
        row = LI()
        for column_number, item in enumerate(row):
            mod_array[item%D][item//D] = (row_number, column_number)

    # print(mod_array)

    Q = II()
    for _ in range(Q):
        L, R = LI()
        ans = 0
        prev_position = mod_array[L%D][L//D]
        for index in range(L//D+1, R//D+1):
        # for position in mod_array[L%D][L//D+1:R//D+1]:
            position = mod_array[L%D][index]
            ans += abs(prev_position[0] - position[0]) + abs(prev_position[1] - position[1])
            prev_position = position
        print(ans)
        


main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    H, W, D = LI()
    mod_array = [[(0,0) for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(H):
        row = LI()
        for column_number, item in enumerate(row):
            mod_array[item%D][item//D] = (row_number, column_number)

    # print(mod_array)

    mod_array_cumsum = [[0 for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(D):
        cumsum = 0
        prev_position = mod_array[row_number][0]
        for column_number in range(1, H*W//D+1):
            position = mod_array[row_number][column_number]
            cumsum += abs(prev_position[0] - position[0]) + abs(prev_position[1] - position[1])
            mod_array_cumsum[row_number][column_number] = cumsum
            prev_position = position

    # print(mod_array_cumsum)

    Q = II()
    for _ in range(Q):
        L, R = LI()
        ans = mod_array_cumsum[L%D][R//D] - mod_array_cumsum[L%D][L//D]
        print(ans)
        

main()
### BUGGY CODE ###

from fractions import*
l=lambda x,y:x//gcd(x,y)*y
n,*a=map(int,open(0).read().split())
s=1
for i in a:s=l(s,i)
print(sum(s//i for i in a)%(10**9+7))

### FIXED CODE ###

from fractions import*
from functools import*
M=10**9+7
_,a=open(0)
*a,=map(int,a.split())
s=reduce(lambda x,y:x//gcd(x,y)*y,a)%M
c=0
for i in a:
    c+=s*pow(i,M-2,M)
    c%=M
print(c)
### BUGGY CODE ###

from sys import setrecursionlimit
setrecursionlimit(1000000) 
N = int(input())
H = list(map(int, input().split()))


def memoize(f):
    cache = {}
    def helper(x):
        if x not in cache:
            cache[x] = f(x)
        return cache[x]
    return helper



def jump(i):
    if i == 0:
        return 0
    a = abs(H[i] - H[i - 1]) + jump(i - 1)
    if i == 1:
        return a
    b = abs(H[i] - H[i - 2]) + jump(i - 2)
    return min(a, b)

memoizedjump = memoize(jump)
print(memoizedjump(N - 1))


### FIXED CODE ###

N = int(input())

H = [int(v) for v in input().strip().split(' ')]

dp = [int(10 ** 10)] * N

dp[0] = 0
dp[1] = abs(H[0] - H[1])

for i in range(2, N):
    dp[i] = min(dp[i], dp[i - 1] + abs(H[i] - H[i - 1]))
    dp[i] = min(dp[i], dp[i - 2] + abs(H[i] - H[i - 2]))

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

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import numpy as np
n, k = map(int, input().split())
s_list = []
a_list = np.zeros((n + 1) * 2, dtype=int)
a_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    s_list.append([l, r + 1])
for i in range(1, n):
    for l, r in s_list:
        a_list[(i+l):(i+r)] += a_list[i]
print(a_list[n] % 998244353)



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
s_list = []
a_list = [0] * (n + 1)
b_list = [0] * (n + 1)
a_list[1] = 1
b_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    s_list.append([l, r + 1])

for i in range(2, n + 1):
    for l, r in s_list:
        t2 = max(0, i - l)
        t1 = max(0, i - r)
        a_list[i] += b_list[t2] - b_list[t1]
    b_list[i] = (b_list[i - 1] + a_list[i]) % 998244353

print(a_list[n] % 998244353)
### BUGGY CODE ###

import collections
N = int(input())
a = list(map(int,input().split()))
a.sort()
array = list(set(a))
sum = 0
for i in range(len(array)):
    if a.count(array[i]) >= array[i]:
        sum += a.count(array[i]) - array[i]
    else:
        sum += a.count(array[i])
print(sum)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
A = a.sort()
array = list(set(a))
array.sort()
sum = 0
n = 0
for i in range(len(array)):
    cnt = 0
    for j in range(n,len(a)):
        if array[i] == a[j]:
            cnt += 1
        else:
            break
    n += cnt
    if cnt >= array[i]:
        sum += cnt - array[i]
    else:
        sum += cnt
print(sum)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
import collections
import math
def comb(n,r):
    if n >= r:
        return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))
    else:
        return 0

for i in range(N):
    a = A[i]
    A[i] = 0
    c = collections.Counter(A)
    values,counts = zip(*c.most_common())
    counts1 = list(counts)
    d = 0
    for j in range(len(counts1)):
        b = comb(counts1[j],2)
        d += b
    print(d)
    A[i] = a

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
import copy
from operator import mul
from functools import reduce

def cmb(n,r):
    if n >= r:
        r = min(n-r,r)
        if r == 0: return 1
        over = reduce(mul, range(n, n - r, -1))
        under = reduce(mul, range(1,r + 1))
        return over // under
    else:
        return 0


s = [0 for i in range(N)]
for i in range(N):
    s[A[i]-1] += 1
    
s1 = copy.copy(s)
for i in range(N):
    if s[i] == 0:
        s1[i] = 0
    else:
        s1[i] -= 1

amount = 0
for i in range(N):
    a = cmb(s[i],2)
    amount += a

for i in range(N):
    print(amount-s1[A[i]-1])
### BUGGY CODE ###

def main():
    n, W, *wv = map(int, open(0).read().split())
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(n):
        w = wv[i * 2]
        v = wv[i * 2 + 1]
        for j in range(0, w):
            dp[i + 1][j] = dp[i][j]
        for j in range(w, W + 1):
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w] + v)
    print(dp[-1][W])

main()

### FIXED CODE ###

from numpy import zeros, maximum            
                                            
n, W, *wv = map(int, open(0).read().split())
t = zeros(W+1, int)                         
for i in range(n):                          
    w = wv[i * 2]                           
    v = wv[i * 2 + 1]                       
    t[w:] = maximum(t[w:], t[:-w]+v)        
print(t[-1])
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
L = []

for a in A:
  L.append(a)
  L = L[::-1]

print(' '.join(map(str, L)))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
print(*A[::-2],*A[N%2::2])
### BUGGY CODE ###

#coding: utf-8
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(1, N):
    M = i if i < K else K
    for k in range(1, M+1):
        dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))
print(dp[N-1])

### FIXED CODE ###

#coding: utf-8
import sys
input = sys.stdin.readline
def main(N, K, h):
    dp = [float("inf")] * N
    dp[0] = 0
    for i in range(1, N):
        dp[i] = min(dp[i], min([dp[i-k] + abs(h[i] - h[i-k]) for k in range(1, min(i, K)+1)]))
    print(dp[N-1])
if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    main(N, K, h)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0

for i in range(n):
    si = s[i]
    for j in range(i+1, n):
        sj = s[j]
        if si == sj:
            continue
        else:
            dif = j - i
            for k in range(j+1, n):
                sk = s[k]
                if dif != k - j and sj != sk and sk != si:
                    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

ans = s.count('R') *  s.count('G') *  s.count('B')

for i in range(n):
    for j in range(i+1, n):
        k = 2 * j - i

        if k >= n:
            break
        elif s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            ans -= 1
         
print(ans)
### BUGGY CODE ###

from itertools import product, permutations,combinations

n = int(input())

# c_hash = {}
c_list = []
# n = 3
for i in range(n):
    s = input()
    c_list.append(''.join(sorted(s)))

# print(sorted(c_list))

c_hash = {}
for c in c_list:
    if c not in c_hash:
        c_hash[c] = 0
    c_hash[c] += 1
count = 0    
for k, v in c_hash.items():
    if v >= 2:
        temp = len(list(combinations(range(v),2)))
        count += temp

print(count)        

### FIXED CODE ###


n = int(input())

# c_hash = {}
c_list = []
# n = 3
for i in range(n):
    s = input()
    c_list.append(''.join(sorted(s)))

# print(sorted(c_list))

c_hash = {}
for c in c_list:
    if c not in c_hash:
        c_hash[c] = 0
    c_hash[c] += 1
count = 0    
for k, v in c_hash.items():
    if v >= 2:

        
        # temp = factorial(v) / factorial(2) / factorial(v - 2)
        # temp = len(list(combinations(range(v),2)))
        temp = v * (v-1)/ 2
        count += temp

print(int(count))