Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
S = list(input())

ch = 0
ans = 0

if N != 0:
    for i in range(N):
        if i == 0:
            if S[i] != S[i+1]:
                ch += 1
            if S[i] == S[i+1] == 'R':
                ans += 1
        elif i == N-1:
            if S[i] == S[i-1] == 'L':
                ans += 1
        else:
            if S[i] != S[i+1]:
                ch += 1
            if S[i] == S[i+1] == 'R' or S[i] == S[i-1] == 'L':
                ans += 1

print(ans+min(K*2,ch))


Fixed submission:
N,K = map(int,input().split())
S = list(input())

ch = 0
ans = 0

if N != 1:
    for i in range(N):
        if i == 0:
            if S[i] != S[i+1]:
                ch += 1
            if S[i] == S[i+1] == 'R':
                ans += 1
        elif i == N-1:
            if S[i] == S[i-1] == 'L':
                ans += 1
        else:
            if S[i] != S[i+1]:
                ch += 1
            if S[i] == S[i+1] == 'R' or S[i] == S[i-1] == 'L':
                ans += 1

print(ans+min(K*2,ch))

Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
S = list(input())

ch = 0
ans = 0
for i in range(N):
    if i == 0:
        if S[i] != S[i+1]:
            ch += 1
        if S[i] == S[i+1] == 'R':
            ans += 1
    elif i == N-1:
        if S[i] == S[i-1] == 'L':
            ans += 1
    else:
        if S[i] != S[i+1]:
            ch += 1
        if S[i] == S[i+1] == 'R' or S[i] == S[i-1] == 'L':
            ans += 1

print(ans+min(K*2,ch))


Fixed submission:
N,K = map(int,input().split())
S = list(input())

ch = 0
ans = 0

if N != 1:
    for i in range(N):
        if i == 0:
            if S[i] != S[i+1]:
                ch += 1
            if S[i] == S[i+1] == 'R':
                ans += 1
        elif i == N-1:
            if S[i] == S[i-1] == 'L':
                ans += 1
        else:
            if S[i] != S[i+1]:
                ch += 1
            if S[i] == S[i+1] == 'R' or S[i] == S[i-1] == 'L':
                ans += 1

print(ans+min(K*2,ch))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = [list(input()) for i in range(N)]
for i in range(N):
    Si = S[i]
    Si.sort()
    Si2 = ''.join(Si)
    S[i] = Si2
ans = 0
for i in range(N-1):
    Si = S[i]
    for j in range(i+1,N):
        Sj = S[j]
        if Si == Sj:
            ans += 1
print(ans)

Fixed submission:
import collections
N = int(input())
S = [list(input()) for i in range(N)]

for i in range(N):
    Si = S[i]
    Si.sort()
    Si2 = ''.join(Si)
    S[i] = Si2

ans = 0
Sc = collections.Counter(S).most_common()
for s in Sc:
    ans += s[1]*(s[1]-1)//2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = [list(input()) for i in range(N)]
for i in range(N):
    Si = S[i]
    Si.sort()
    S[i] = Si
ans = 0
for i in range(N-1):
    Si = S[i]
    for j in range(i+1,N):
        Sj = S[j]
        if Si == Sj:
            ans += 1
print(ans)

Fixed submission:
import collections
N = int(input())
S = [list(input()) for i in range(N)]

for i in range(N):
    Si = S[i]
    Si.sort()
    Si2 = ''.join(Si)
    S[i] = Si2

ans = 0
Sc = collections.Counter(S).most_common()
for s in Sc:
    ans += s[1]*(s[1]-1)//2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import collections
N = int(input())
S = [list(input()) for i in range(N)]
ans = 0
for i in range(N-1):
    Si = collections.Counter(S[i]).most_common()
    Si.sort(key=lambda x: x[0])
    for j in range(i+1,N):
        Sj = collections.Counter(S[j]).most_common()
        Sj.sort(key=lambda x: x[0])
        if Si == Sj:
            ans += 1
print(ans)


Fixed submission:
import collections
N = int(input())
S = [list(input()) for i in range(N)]

for i in range(N):
    Si = S[i]
    Si.sort()
    Si2 = ''.join(Si)
    S[i] = Si2

ans = 0
Sc = collections.Counter(S).most_common()
for s in Sc:
    ans += s[1]*(s[1]-1)//2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

S = readline().rstrip()
S = S[::-1]
dp = [0]*13
dp[0] = 1
pow10 = 4
for i,s in enumerate(S):
    dpnew = [0]*13
    pow10 = pow10*10%13
    if s != '?':
        k = int(s)
        for j in range(13):
            dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    else:
        for k in range(10):
            for j in range(13):
                dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    dp = dpnew

print(dp[5])


Fixed submission:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

S = readline().rstrip()
S = S[::-1]
dp = [0]*13
dp[0] = 1

for i,s in enumerate(S):
    dpnew = [0]*13
    pow10 = pow(10,i,13)
    if s != '?':
        k = int(s)
        for j in range(13):
            dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    else:
        for k in range(10):
            for j in range(13):
                dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    dp = dpnew

print(dp[5])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

S = readline().rstrip()
S = S[::-1]
dp = [0]*13
dp[0] = 1

for i,s in enumerate(S):
    dpnew = [0]*13
    if s != '?':
        k = int(s)
        for j in range(13):
            dpnew[(k*(10**i)+j)%13] = (dpnew[(k*(10**i)+j)%13]+dp[j])%mod
    else:
        for k in range(10):
            for j in range(13):
                dpnew[(k*(10**i)+j)%13] = (dpnew[(k*(10**i)+j)%13]+dp[j])%mod
    dp = dpnew

print(dp[5])


Fixed submission:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

S = readline().rstrip()
S = S[::-1]
dp = [0]*13
dp[0] = 1

for i,s in enumerate(S):
    dpnew = [0]*13
    pow10 = pow(10,i,13)
    if s != '?':
        k = int(s)
        for j in range(13):
            dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    else:
        for k in range(10):
            for j in range(13):
                dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    dp = dpnew

print(dp[5])
Buggy python submission (verdict: Time Limit Exceeded):
S = int(input())
j = 0
for i in range(int(S**0.5),0,-1):
    if S%i == 0:
        j = S//i
        break

print(0,0,i,0,0,j)


Fixed submission:
S = int(input())

y = (S+10**9-1)//10**9
x = y*(10**9)-S

print(0,0,10**9,1,x,y)
Buggy python submission (verdict: Runtime Error):
import collections

N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            pq.append((xy[i][0]-xy[j][0], xy[i][1]-xy[j][1]))
#print(pq)
pqc = collections.Counter(pq)
x = pqc.most_common()[0][1]
print(N-x)


Fixed submission:
import collections
import sys

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

if N == 1:
    print(1)
    sys.exit()

pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            pq.append((xy[i][0]-xy[j][0], xy[i][1]-xy[j][1]))
#print(pq)
pqc = collections.Counter(pq)
x = pqc.most_common()[0][1]
print(N-x)
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
a = [int(input()) for m in range(M)]
ans = []
P = 10**9+7
for n in range(N):
    if n+1 in a:
        ans.append(0)
    else:
        if n == 0:
            ans.append(1)
        elif n == 1:
            ans.append(ans[0]+1)
        else:
            ans.append((ans[n-1]+ans[n-2])%P)
print(ans[N-1])


Fixed submission:
from collections import deque
N,M = map(int,input().split())
a = deque([int(input()) for m in range(M)]+[-1])
ans = []
P = 10**9+7
for n in range(N):
    if n+1 == a[0]:
        ans.append(0)
        a.popleft()
    else:
        if n == 0:
            ans.append(1)
        elif n == 1:
            ans.append(ans[0]+1)
        else:
            ans.append((ans[n-1]+ans[n-2])%P)
print(ans[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,M = map(int,input().split())
a = [int(input()) for m in range(M)]
ans = []
P = 10**9+7
for n in range(N):
    if n+1 in a:
        ans.append(0)
    else:
        if n == 0:
            ans.append(1)
        elif n == 1:
            ans.append(ans[0]+1)
        else:
            ans.append((ans[n-1]+ans[n-2])%P)
print(ans[N-1])


Fixed submission:
from collections import deque
N,M = map(int,input().split())
a = deque([int(input()) for m in range(M)]+[-1])
ans = []
P = 10**9+7
for n in range(N):
    if n+1 == a[0]:
        ans.append(0)
        a.popleft()
    else:
        if n == 0:
            ans.append(1)
        elif n == 1:
            ans.append(ans[0]+1)
        else:
            ans.append((ans[n-1]+ans[n-2])%P)
print(ans[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,M = map(int,input().split())
a = deque([int(input()) for m in range(M)])
ans = []
P = 10**9+7
for n in range(N):
    if n+1 in a:
        ans.append(0)
        a.popleft()
    else:
        if n == 0:
            ans.append(1)
        elif n == 1:
            ans.append(ans[0]+1)
        else:
            ans.append((ans[n-1]+ans[n-2])%P)
print(ans[N-1])


Fixed submission:
from collections import deque
N,M = map(int,input().split())
a = deque([int(input()) for m in range(M)]+[-1])
ans = []
P = 10**9+7
for n in range(N):
    if n+1 == a[0]:
        ans.append(0)
        a.popleft()
    else:
        if n == 0:
            ans.append(1)
        elif n == 1:
            ans.append(ans[0]+1)
        else:
            ans.append((ans[n-1]+ans[n-2])%P)
print(ans[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
N = len(S)
ans = 0
while True:
    i = S.find('ABC')
    if i == -1:
        break
    elif i == 0:
        S = 'BCA' + S[i+3:]
        ans += 1
    elif i == N-3:
        S = S[:i]+'BCA'
        ans += 1
    else:
        S = S[:i]+'BCA'+S[i+3:]
        ans += 1
print(ans)

Fixed submission:
S = list(input())
N = len(S)

if S[0] == 'A':
    ac = 1
else:
    ac = 0

ans = 0
for i in range(1,N):
    if S[i] == 'A':
        if S[i-1] != 'A':
            ac = 1
        else:
            ac += 1
    elif S[i] == 'B':
        if S[i-1] != 'A':
            ac = 0
    else:
        if S[i-1] == 'B':
            ans += ac
            S[i] = 'A'
        else:
            ac = 0

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
N = len(S)
ans = 0
while True:
    i = S.find('ABC')
    if i == -1:
        break
    elif i == 0:
        S = 'BCA' + S[i+3:]
        ans += 1
    elif i == N-3:
        S = S[:i]+'BCA'
        ans += 1
    else:
        S = S[:i]+'BCA'+S[i+3:]
        ans += 1
print(ans)

Fixed submission:
S = list(input())
N = len(S)

if S[0] == 'A':
    ac = 1
else:
    ac = 0

ans = 0
for i in range(1,N):
    if S[i] == 'A':
        if S[i-1] != 'A':
            ac = 1
        else:
            ac += 1
    elif S[i] == 'B':
        if S[i-1] != 'A':
            ac = 0
    else:
        if S[i-1] == 'B':
            ans += ac
            S[i] = 'A'
        else:
            ac = 0

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S = list(input())
N = len(S)
b = True
ans = 0
while b:
    b = False
    for i in range(N-2):
        if S[i] == 'A' and S[i+1] == 'B' and S[i+2] == 'C':
            b = True
            S[i] = 'B'
            S[i+1] = 'C'
            S[i+2] = 'A'
            ans += 1
print(ans)


Fixed submission:
S = list(input())
N = len(S)

if S[0] == 'A':
    ac = 1
else:
    ac = 0

ans = 0
for i in range(1,N):
    if S[i] == 'A':
        if S[i-1] != 'A':
            ac = 1
        else:
            ac += 1
    elif S[i] == 'B':
        if S[i-1] != 'A':
            ac = 0
    else:
        if S[i-1] == 'B':
            ans += ac
            S[i] = 'A'
        else:
            ac = 0

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S = list(input())
N = len(S)
b = True
ans = 0
while b:
    b = False
    for i in range(N-2):
        if S[i] == 'A' and S[i+1] == 'B' and S[i+2] == 'C':
            b = True
            S[i] = 'B'
            S[i+1] = 'C'
            S[i+2] = 'A'
            ans += 1
print(ans)


Fixed submission:
S = list(input())
N = len(S)

if S[0] == 'A':
    ac = 1
else:
    ac = 0

ans = 0
for i in range(1,N):
    if S[i] == 'A':
        if S[i-1] != 'A':
            ac = 1
        else:
            ac += 1
    elif S[i] == 'B':
        if S[i-1] != 'A':
            ac = 0
    else:
        if S[i-1] == 'B':
            ans += ac
            S[i] = 'A'
        else:
            ac = 0

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,N = map(int,input().split())

ans = 0
for b in range(N+1):
    for g in range(N+1):
        if N-B*b-G*g < 0:
            break
        if (N-B*b-G*g)%R == 0:
            ans += 1
print(ans)


Fixed submission:
R,G,B,N = map(int,input().split())

li = [R,G,B]
li.sort(reverse=True)
R = li[0]
G = li[1]
B = li[2]
#print(R,G,B)

ans = 0
for b in range(N//B+1):
    for g in range((N-B*b)//G+1):
        if N-B*b-G*g >= 0 and (N-B*b-G*g)%R == 0:
            ans += 1
print(ans)

Buggy python submission (verdict: Runtime Error):
R,G,B,N = map(int,input().split())

ans = 0
for b in range(N+1):
    for g in range((N+1):
        if N-B*b-G*g >= 0 and (N-B*b-G*g)%R == 0:
            ans += 1
print(ans)



Fixed submission:
R,G,B,N = map(int,input().split())

li = [R,G,B]
li.sort(reverse=True)
R = li[0]
G = li[1]
B = li[2]
#print(R,G,B)

ans = 0
for b in range(N//B+1):
    for g in range((N-B*b)//G+1):
        if N-B*b-G*g >= 0 and (N-B*b-G*g)%R == 0:
            ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,N = map(int,input().split())

li = [R,G,B]
li.sort(reverse=True)
R = li[0]
G = li[1]
B = li[2]
#print(R,G,B)

ans = 0
for b in range(N//B+1):
    for g in range((N-B*b)//G+1):
        if N-B*b-G*g >= 0 and (N-B*b-G*g)%R == 0:
            ans += 1
print(ans)


Fixed submission:
R,G,B,N = map(int,input().split())

li = [R,G,B]
li.sort(reverse=True)
R = li[0]
G = li[1]
B = li[2]
#print(R,G,B)

ans = 0
for b in range(N//B+1):
    for g in range((N-B*b)//G+1):
        if N-B*b-G*g >= 0 and (N-B*b-G*g)%R == 0:
            ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,N = map(int,input().split())

li = [R,G,B]
li.sort()
R = li[0]
G = li[1]
B = li[2]
#print(R,G,B)

ans = 0
for b in range(N//B+1):
    for g in range((N-B*b)//G+1):
        if N-B*b-G*g >= 0 and (N-B*b-G*g)%R == 0:
            ans += 1
print(ans)


Fixed submission:
R,G,B,N = map(int,input().split())

li = [R,G,B]
li.sort(reverse=True)
R = li[0]
G = li[1]
B = li[2]
#print(R,G,B)

ans = 0
for b in range(N//B+1):
    for g in range((N-B*b)//G+1):
        if N-B*b-G*g >= 0 and (N-B*b-G*g)%R == 0:
            ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def gridbfs(grid):
    INF = 10**18

    gridy = len(grid)
    gridx = len(grid[0])

    dist = [[INF]*gridx for _ in range(gridy)]
    q = deque()
    for y in range(gridy):
        for x in range(gridx):
            if grid[y][x] == '#':
                dist[y][x] = 0
                q.append((y,x))

    while q:
        y,x = q.popleft()
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < gridy and 0 <= nx < gridx):
                continue
            if dist[ny][nx] != INF:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny,nx))

    return dist

H,W = map(int,input().split())
Grid = [input() for _ in range(H)]
d = gridbfs(Grid)
print(max(max(d[i]) for i in range(H)))


Fixed submission:
from collections import deque
H,W = map(int,input().split())
A = [list(input()) for i in range(H)]

q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append((i, j))
ans = -1

while len(q) != 0:
    ans += 1
    qq = []
    while len(q) != 0:
        t = q.popleft()
        i,j = t[0],t[1]
        if i > 0 and A[i-1][j] == '.':
            qq.append((i-1,j))
            A[i-1][j] = '#'
        if j > 0 and A[i][j-1] == '.':
            qq.append((i,j-1))
            A[i][j-1] = '#'
        if i < H-1 and A[i+1][j] == '.':
            qq.append((i+1,j))
            A[i+1][j] = '#'
        if j < W-1 and A[i][j+1] == '.':
            qq.append((i,j+1))
            A[i][j+1] = '#'
    q = deque(qq)

print(ans)
Buggy python submission (verdict: Runtime Error):
A,B=map(int,input()split())
print(max(A*(A-1),A*B,B*(B-1)))


Fixed submission:
A,B=map(int,input().split())
print(max(A+(A-1),A+B,B+(B-1)))
Buggy python submission (verdict: Runtime Error):
from collection import Counter
n = int(input())
s = input()

mod = 10**9+7

scnt = Counter(s).most_common()
ans = 1

for i in range(len(scnt)):
    ans = ans*scnt[i][1]%p
ans = (ans - 1 + p)%p
print(ans)

Fixed submission:
from collections import Counter
n = int(input())
s = input()

mod = 10**9+7

scnt = Counter(s).most_common()
ans = 1

for i in range(len(scnt)):
    ans = ans*(scnt[i][1]+1)%mod
ans = (ans - 1 + mod)%mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]

T = [int(input()) for _ in range(B)]

X = [int(input()) for _ in range(Q)]

from bisect import bisect_left

for _ in range(Q):
    ans = 10**12
    x = X[_]
    idxs = bisect_left(S,x)
    idxt = bisect_left(T,x)

    if idxs < A and idxt < B:
        ans = min(ans, max(S[idxs],T[idxt])-x)
    if 0 <= idxs-1 and 0 <= idxt-1:
        ans = min(ans, x-min(S[idxs-1],T[idxt-1]))
    if idxs < A and 0 <= idxt-1:
        ans = min(ans, S[idxs]-T[idxt-1] + min(S[idxs]-x, x-T[idxt-1]))
    if idxt < B and 0 <= idxs-1:
        ans = min(ans, T[idxt]-S[idxs-1] + min(T[idxt]-x, x-S[idxs-1]))

    print(ans)



Fixed submission:
A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]

T = [int(input()) for _ in range(B)]

from bisect import bisect_left

for _ in range(Q):
    ans = 10**12
    x = int(input())
    idxs = bisect_left(S,x)
    idxt = bisect_left(T,x)

    if idxs < A and idxt < B:
        ans = min(ans, max(S[idxs],T[idxt])-x)
    if 0 <= idxs-1 and 0 <= idxt-1:
        ans = min(ans, x-min(S[idxs-1],T[idxt-1]))
    if idxs < A and 0 <= idxt-1:
        ans = min(ans, S[idxs]-T[idxt-1] + min(S[idxs]-x, x-T[idxt-1]))
    if idxt < B and 0 <= idxs-1:
        ans = min(ans, T[idxt]-S[idxs-1] + min(T[idxt]-x, x-S[idxs-1]))
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]

T = [int(input()) for _ in range(B)]

from bisect import bisect_left

for _ in range(Q):
    ans = 10**12
    x = int(input())
    idxs = bisect_left(S,x)
    idxt = bisect_left(T,x)

    if idxs < A and idxt < B:
        ans = min(ans, max(S[idxs],T[idxt])-x)
    if 0 <= idxs-1 and 0 <= idxt-1:
        ans = min(ans, x-min(S[idxs-1],T[idxt-1]))
    if idxs < A and 0 <= idxt-1:
        ans = min(ans, S[idxs]-T[idxt-1] + min(S[idxs]-x, x-T[idxt-1]))
    if idxt < B and 0 <= idxs-1:
        ans = min(ans, T[idxt]-S[idxs-1] + min(T[idxt]-x, x-S[idxs-1]))
    print(ans)


Fixed submission:
A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]

T = [int(input()) for _ in range(B)]

from bisect import bisect_left

for _ in range(Q):
    ans = 10**12
    x = int(input())
    idxs = bisect_left(S,x)
    idxt = bisect_left(T,x)

    if idxs < A and idxt < B:
        ans = min(ans, max(S[idxs],T[idxt])-x)
    if 0 <= idxs-1 and 0 <= idxt-1:
        ans = min(ans, x-min(S[idxs-1],T[idxt-1]))
    if idxs < A and 0 <= idxt-1:
        ans = min(ans, S[idxs]-T[idxt-1] + min(S[idxs]-x, x-T[idxt-1]))
    if idxt < B and 0 <= idxs-1:
        ans = min(ans, T[idxt]-S[idxs-1] + min(T[idxt]-x, x-S[idxs-1]))
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
h = list(map(int,input().split()))
INF = 10**10
dp = [INF for i in range(N)]
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2,N):
    for j in range(max(0,i-K),i):
        dp[i] = min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[N-1])


Fixed submission:
N,K = map(int,input().split())
h = list(map(int,input().split()))
INF = 10**10
dp = [INF for i in range(N)]
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2,N):
    for j in range(max(0,i-K),i):
        dp[i] = min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
t = input()

def LCS(X,Y):
    XL = len(X)
    YL = len(Y)
    dp = [[0 for j in range(YL+1)] for i in range(XL+1)]
    for i in range(XL):
        for j in range(YL):
            if X[i] == Y[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
    # 以下復元
    idx = dp[XL][YL]-1
    S = [0 for i in range(idx+1)]
    i,j = XL,YL
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            i -= 1
            j -= 1
            S[idx] = X[i]
            idx -= 1
    return S

print(''.join(LCS(s,t)))


Fixed submission:
s = input()
t = input()

def LCS(X,Y):
    XL = len(X)
    YL = len(Y)
    dp = [[0 for j in range(YL+1)] for i in range(XL+1)]
    for i in range(XL):
        for j in range(YL):
            if X[i] == Y[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
    # 以下復元
    idx = dp[XL][YL]-1
    S = [0 for i in range(idx+1)]
    i,j = XL,YL
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            i -= 1
            j -= 1
            S[idx] = X[i]
            idx -= 1
    return S

print(''.join(LCS(s,t)))
Buggy python submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N = int(readline())
k = -1
for i in range(1,1000):
    if i*(i-1)//2 == N:
        k = i
        print('Yes')
        break
if k == -1:
    print('No')
    exit()

print(k)
ans = [[] for i in range(k)]

import itertools

for i,(a,b) in enemurate(itertools.combinations(range(k),2),1):
    ans[a].append(i)
    ans[b].append(i)

for aaa in ans:
    print(len(aaa),' '.join(map(str,aaa)))



Fixed submission:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N = int(readline())

for i in range(1,1000):
    if i*(i-1)//2 == N:
        k = i
        print('Yes')
        break
    if i == 999:
        print('No')
        exit()

print(k)
ans = [[] for i in range(k)]

now = 1

import itertools
L = [i for i in range(k)]
for v in itertools.combinations(L,2):
    ans[v[0]].append(now)
    ans[v[1]].append(now)
    now += 1
for aaa in ans:
    print(len(aaa),' '.join(map(str,aaa)))