Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(input())

ans = 0

for n in range(1000):
    pin = str(n).zfill(3)
    head = 0
    for c in S:
        if c == pin[head]:
            head += 1
        if head == 3:
            ans += 1
            break

print(ans)


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

ans = 0

for n in range(1000):
    pin = str(n).zfill(3)
    head = 0
    for c in S:
        if c == pin[head]:
            head += 1
        if head == 3:
            ans += 1
            break

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(input())

ans = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            head = 0
            pin = [i, j, k]
            for c in S:
                if c == str(pin[head]):
                    head += 1
                if head == 3:
                    ans += 1
                    break

print(ans)


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

ans = 0

for n in range(1000):
    pin = str(n).zfill(3)
    head = 0
    for c in S:
        if c == pin[head]:
            head += 1
        if head == 3:
            ans += 1
            break

print(ans)

Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(2000)

N = int(input())
S = list(input())

pattern = set()

def generate_pwd(cnt, lucky_num):
    if len(lucky_num) == 3:
        pattern.add(''.join(lucky_num))
        return
    if cnt > 3:
        return
    
    generate_pwd(cnt, lucky_num[:cnt] + lucky_num[cnt + 1:])
    generate_pwd(cnt + 1, lucky_num)

    return

generate_pwd(0, S)
print(len(pattern))
        


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

ans = 0

for n in range(1000):
    pin = str(n).zfill(3)
    head = 0
    for c in S:
        if c == pin[head]:
            head += 1
        if head == 3:
            ans += 1
            break

print(ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
S = list(input())

pattern = set()

def generate_pwd(cnt, lucky_num):
    if len(lucky_num) == 3:
        pattern.add(''.join(lucky_num))
        return
    if cnt > 3:
        return
    
    generate_pwd(cnt, lucky_num[:cnt] + lucky_num[cnt + 1:])
    generate_pwd(cnt + 1, lucky_num)

    return

generate_pwd(0, S)
print(len(pattern))
        


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

ans = 0

for n in range(1000):
    pin = str(n).zfill(3)
    head = 0
    for c in S:
        if c == pin[head]:
            head += 1
        if head == 3:
            ans += 1
            break

print(ans)
Buggy python submission (verdict: Runtime Error):
days = ['SUN', 'MON', 'TUE', 'WED', 'THU',' FRI', 'SAT']
S = input()
print(7 - days.index(S))

Fixed submission:
days = ['SUN', 'MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT']
S = input()
print(7 - days.index(S))
Buggy python submission (verdict: Runtime Error):
n, t = map(int, input().split())
dish = [list(map(int, input().split())) for _ in range(n)]
dish.sort(key=lambda x: x[0])
dp = [[0 for _ in range(3000)] for _ in range(3000)]
ans = 0

for i in range(n):
    for j in range(t):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        nj = j + dish[i][0]
        if nj < t:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + dish[i][1])
    now = dp[i][t- 1] + dish[i][1]
    ans = max(ans, now)

print(ans)

Fixed submission:
n, t = map(int, input().split())
dish = [list(map(int, input().split())) for _ in range(n)]
dish.sort(key=lambda x: x[0])
dp = [[0 for _ in range(3005)] for _ in range(3005)]

ans = 0
for i in range(n):
    for j in range(t):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        nj = j + dish[i][0]
        if nj < t:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + dish[i][1])
    now = dp[i][t- 1] + dish[i][1]
    ans = max(ans, now)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, t = map(int, input().split())
dish = [list(map(int, input().split())) for _ in range(n)]
dish.sort(key=lambda x: x[0])
dp = [[0 for _ in range(3000)] for _ in range(3000)]
ans = 0

for i in range(n):
    for j in range(t):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        nj = j + dish[i][0]
        if nj < t:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + dish[i][1])
    now = dp[i][t- 1] + dish[i][1]
    ans = max(ans, now)

print(ans)

Fixed submission:
n, t = map(int, input().split())
dish = [list(map(int, input().split())) for _ in range(n)]
dish.sort(key=lambda x: x[0])
dp = [[0 for _ in range(3005)] for _ in range(3005)]

ans = 0
for i in range(n):
    for j in range(t):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        nj = j + dish[i][0]
        if nj < t:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + dish[i][1])
    now = dp[i][t- 1] + dish[i][1]
    ans = max(ans, now)

print(ans)
Buggy python submission (verdict: Runtime Error):
def check():
  n = int(input())
  if n <= 9:
    return 'Yes'
  elif n > 81:
    return 'No'
  else:
    for i in range(2, 9):
      q, mod = divmod(n, i)
      if mod == 0 and q <= 9:
        return 'Yes'
    return 'No'

print(check())


Fixed submission:
a, b = map(int, input().split())
if a < 10 and b < 10:
  print(a * b)
else:
  print(-1)

Buggy python submission (verdict: Runtime Error):
a = int(input())
b = int(input())
if a < 10 and b < 10:
  print(a * b)
else:
  print(-1)


Fixed submission:
a, b = map(int, input().split())
if a < 10 and b < 10:
  print(a * b)
else:
  print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
def work_through(): 
  i, j = 1, 1
  cnt = 0

  arr = []
  arr.append([i, j])

  n = int(input())

  while True:
    tmp = []
    length = len(arr)
    for i in range(0, length):
      x, y = arr.pop()
      if x * y == n:
        return cnt
      tmp.append([x + 1, y])
      tmp.append([x, y + 1])
    arr = tmp
    cnt += 1

print(work_through())

Fixed submission:
import math

INF = 1e12
n = int(input())
cnt = INF
m = math.sqrt(n)

for i in range(1, math.ceil(m) + 1):
  if n % i == 0:
    j = n // i
    cnt = min(cnt, i + j - 2)
  else:
    continue

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(n - 2):
    a = L[i]
    for j in range(i + 1, n - 1):
        b = L[j]
        for k in range(j + 1, n):
            c = L[k]
            if c >= a + b:
                break
            ans += 1
print(ans)


Fixed submission:
n = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(n - 2):
    a = L[i]
    k = i
    for j in range(i + 1, n - 1):
        b = L[j]
        while k < n and L[k] < a + b:
            k += 1
        ans += k - (j + 1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int, input().split()))
ans = list()
for i in range(1, N + 1):
    ans.append(str(a.index(i) + 1))
print(' '.join(ans))

Fixed submission:
N = int(input())
a = list(map(int, input().split()))
ans = [-1] * N
for i in range(N):
    ai = a[i]
    ans[ai - 1] = str(i + 1)
print(' '.join(ans))
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
INF = 10 ** 5 * 12
dp = [INF] * (1 << n)
dp[0] = 0
keys = []

for _ in range(m):
    a, b = map(int, input().split())
    s = 0
    for c in list(map(int, input().split())):
        s |= 1 << (c - 1)
    keys.append([s, a])

for s in range(1 << n):
    for i in range(m):
        to = s | keys[i][0]
        cost = dp[s] + keys[i][1]
        dp[to] = min(dp[to], cost)

ans = dp[-1] if dp[-1] != INF else -1
print(ans)


Fixed submission:
n, m = map(int, input().split())
keys = []
INF = 10 ** 5 * 12
dp = [INF] * (1 << n)
dp[0] = 0

for _ in range(m):
    a, b = map(int, input().split())
    s = 0
    for c in list(map(int, input().split())):
        s |= 1 << (c - 1)
    keys.append([s, a])

for s in range(1 << n):
    for i in range(m):
        to = s | keys[i][0]
        cost = dp[s] + keys[i][1]
        dp[to] = min(dp[to], cost)

ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
keys = []
INF = 10 ** 5 * 12
dp = [INF] * (1 << n)
dp[0] = 0

for _ in range(m):
    a, b = map(int, input().split())
    s = 0
    for c in list(map(int, input().split())):
        s |= 1 << (c - 1)
    keys.append([s, a])

for s in range(1 << n):
    for i in range(m):
        to = s | keys[i][0]
        cost = dp[s] + keys[i][1]
        dp[to] = min(dp[to], cost)

ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)


Fixed submission:
n, m = map(int, input().split())
keys = []
INF = 10 ** 5 * 12
dp = [INF] * (1 << n)
dp[0] = 0

for _ in range(m):
    a, b = map(int, input().split())
    s = 0
    for c in list(map(int, input().split())):
        s |= 1 << (c - 1)
    keys.append([s, a])

for s in range(1 << n):
    for i in range(m):
        to = s | keys[i][0]
        cost = dp[s] + keys[i][1]
        dp[to] = min(dp[to], cost)

ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [i for i in range(1, n + 1)]
print(sum(a) - n)

Fixed submission:
n = int(input())
ans = n * (n + 1) // 2 - n
print(ans)
Buggy python submission (verdict: Runtime Error):
n, q = map(int, input().split())
node = [[] for _ in range(n)]
ans = [0] * n

def score(p, c):
    ans[p] += c
    for child in node[p]:
        score(child, ans[p])

for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    node[a].append(b)

for _ in range(q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x

score(0, 0)
print(*ans)


Fixed submission:
n, q = map(int, input().split())
node = [[] for _ in range(n)]
ans = [0] * n

for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    node[a].append(b)
    node[b].append(a)

for _ in range(q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x

not_yet = [True] * n
not_yet[0] = False
stack = [0]
while stack:
    parent = stack.pop()
    for child in node[parent]:
        if not_yet[child]:
            ans[child] += ans[parent]
            not_yet[child] = False
            stack.append(child)

print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
s = [''.join(sorted(list(input()))) for _ in range(N)]
flag = [False] * N
ans = 0
for i in range(N - 1):
    if flag[i]:
        continue
    flag[i] = True
    cnt = 0
    for j in range(i + 1, N):
        if s[i] == s[j]:
            flag[j] = True
            cnt += 1
    ans += sum([n for n in range(cnt, 0, -1)])

print(ans)
    

Fixed submission:
N = int(input())
cnt_dict = dict()

for _ in range(N):
    s = ''.join(sorted(list(input())))
    if s in cnt_dict:
        cnt_dict[s] += 1
    else:
        cnt_dict[s] = 1

ans = 0
for cnt in cnt_dict.values():
    ans += cnt * (cnt - 1) // 2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
s = [''.join(sorted(list(input()))) for _ in range(N)]
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
       if s[i] == s[j]:
           ans += 1

print(ans)
    

Fixed submission:
N = int(input())
cnt_dict = dict()

for _ in range(N):
    s = ''.join(sorted(list(input())))
    if s in cnt_dict:
        cnt_dict[s] += 1
    else:
        cnt_dict[s] = 1

ans = 0
for cnt in cnt_dict.values():
    ans += cnt * (cnt - 1) // 2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = list(input())
n = len(s)
ans = [0] * n
for i in range(n):
    if s[i] == 'R':
        l = s[i:].index('L')
        if l % 2 == 0:
            ans[i + l] += 1
        else:
            ans[i + l - 1] += 1
    else:
        r = s[::-1][n - 1 - i:].index('R')
        if r % 2 == 0:
            ans[i - r] += 1
        else:
            ans[i - r + 1] += 1

print(*ans)

Fixed submission:
s = list(input())
n = len(s)
ans = [0] * n
rs = []
ls = []

for i, c in enumerate(s):
    if c == 'R':
        rs.append(i)
    else:
        ls.append(i)

p = 0
for i, l in enumerate(ls):
    ans[l] += (l - p) // 2
    ans[l - 1] += (l - p) // 2
    if (l - p) % 2 == 1:
        ans[l - 1] += 1
    if l + 1 < n:
        p = l + 1

p = n - 1
rs = rs[::-1]
for i, r in enumerate(rs):
    ans[r] += (p - r) // 2
    ans[r + 1] += (p - r) // 2
    if (p - r) % 2 == 1:
        ans[r + 1] += 1
    if r - 1 >= 0:
        p = r - 1

print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = [int(input()) for _ in range(N)]
for i in range(N):
    front = a[:i]
    back = a[i + 1:]
    f_max = max(front) if front else 0
    b_max = max(back) if back else 0
    print(max(f_max, b_max))

Fixed submission:
N = int(input())
a = list()
tmp = [0, 0]

for _ in range(N):
    ai = int(input())
    a.append(ai)
    if ai > tmp[1]:
        tmp[1] = ai
    elif ai > tmp[0]:
        tmp[0] = ai

m = tmp[1]

for ai in a:
    ans = m
    if ai == m:
        ans = tmp[0]
    print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
broken_step = [0] * N
for _ in range(M):
    n = int(input())
    broken_step[n - 1] = 1

dp = [0] * N

dp[0] = 0 if broken_step[0] == 1 else 1
dp[1] = 0 if broken_step[1] == 1 else (1 + dp[0])

for i in range(2, N):
    if broken_step[i] == 1:
        dp[i] = 0
    else:
        dp[i] = dp[i - 1] + dp[i - 2]

print(dp[-1] % 1000000007)


Fixed submission:
N, M = map(int, input().split())
broken_step = [0] * (N + 1)
for _ in range(M):
    n = int(input())
    broken_step[n] = 1

dp = [1] * (N + 1)
dp[1] = 0 if broken_step[1] == 1 else dp[0]

for i in range(2, N + 1):
    if broken_step[i] == 1:
        dp[i] = 0
    else:
        dp[i] = dp[i -1] + dp[i - 2]

print(dp[-1] % 1000000007)

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
bs = [int(input()) for _ in range(M)]
bi = 0
pattern = [-1] * N

if bi < M and 1 == bs[bi]:
    pattern[0] = 0
    bi += 1
else:
    pattern[0] = 1

if bi < M and 2 == bs[bi]:
    pattern[1] = 0
    bi += 1
else:
    pattern[1] = 1 + pattern[0]

for i in range(2, N):
    if bi < M and (i + 1) == bs[bi]:
        pattern[i] = 0
        bi += 1
    else:
        pattern[i] = pattern[i -1] + pattern[i - 2]

print(pattern[-1] % 1000000007)


Fixed submission:
N, M = map(int, input().split())
broken_step = [0] * (N + 1)
for _ in range(M):
    n = int(input())
    broken_step[n] = 1

dp = [1] * (N + 1)
dp[1] = 0 if broken_step[1] == 1 else dp[0]

for i in range(2, N + 1):
    if broken_step[i] == 1:
        dp[i] = 0
    else:
        dp[i] = dp[i -1] + dp[i - 2]

print(dp[-1] % 1000000007)

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
broken_steps = [int(input()) for _ in range(M)]
pattern = [-1] * N
pattern[0] = 0 if 1 in broken_steps else 1
pattern[1] = 0 if 2 in broken_steps else 1 + pattern[0]

for i in range(2, N):
    pattern[i] = 0 if (i + 1) in broken_steps else (pattern[i -2] + pattern[i - 1])

print(pattern[-1] % 1000000007)


Fixed submission:
N, M = map(int, input().split())
broken_step = [0] * (N + 1)
for _ in range(M):
    n = int(input())
    broken_step[n] = 1

dp = [1] * (N + 1)
dp[1] = 0 if broken_step[1] == 1 else dp[0]

for i in range(2, N + 1):
    if broken_step[i] == 1:
        dp[i] = 0
    else:
        dp[i] = dp[i -1] + dp[i - 2]

print(dp[-1] % 1000000007)
Buggy python submission (verdict: Time Limit Exceeded):
import re
s = input()
cnt = 0
while 'ABC' in s:
    s = re.sub(r'ABC', 'BCA', s, count=1)
    cnt += 1

print(cnt)

Fixed submission:
import re
s = input()
sub = re.sub('BC', 'X', s)

ans = 0
a = 0
for i in range(len(sub)):
    if sub[i] == 'A':
        a += 1
    elif sub[i] == 'X':
        ans += a
    else:
        a = 0

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
path = set([n for n in range(1, N + 1)])
for _ in range(M):
    l, r = map(int, input().split())
    pi = set([n for n in range(l, r + 1)])
    path &= pi
print(len(path))

Fixed submission:
N, M = map(int, input().split())
l, r = 1, 10 ** 5

for _ in range(M):
    li, ri = map(int, input().split())
    l = max(l, li)
    r = min(r, ri)

ans = r - l + 1 if r >= l else 0
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = list(input())
cnt = [0] * (N)

last = S[0]
for i in range(1, N):
    c = S[i]
    if (last + c) == 'AC':
        cnt[i] = 1
    last = c

for _ in range(Q):
    l, r = map(int, input().split())
    ans = sum(cnt[l:r])
    print(ans)


Fixed submission:
N, Q = map(int, input().split())
S = list(input())
cnt = [0] * (N)

for i in range(1, N):
    if S[i - 1] + S[i] == 'AC':
        cnt[i] = cnt[i - 1] + 1
    else:
        cnt[i] = cnt[i - 1]

for _ in range(Q):
    l, r = map(int, input().split())
    ans = cnt[r - 1] - cnt[l - 1]
    print(ans)

Buggy python submission (verdict: Runtime Error):
N, Q = map(int, input().split())
S = list(input())
cnt = [0] * (N - 1)

last = ''
for i in range(N):
    c = S[i]
    if (last + c) == 'AC':
        cnt[i] = 1
    last = c

for _ in range(Q):
    l, r = map(int, input().split())
    ans = sum(cnt[l - 1:r - 1])
    print(ans)

Fixed submission:
N, Q = map(int, input().split())
S = list(input())
cnt = [0] * (N)

for i in range(1, N):
    if S[i - 1] + S[i] == 'AC':
        cnt[i] = cnt[i - 1] + 1
    else:
        cnt[i] = cnt[i - 1]

for _ in range(Q):
    l, r = map(int, input().split())
    ans = cnt[r - 1] - cnt[l - 1]
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = list(input())
cnt = [0] * (N - 1)

for i in range(N - 1):
    if S[i] + S[i + 1] == 'AC':
        cnt[i] = 1

for _ in range(Q):
    l, r = map(int, input().split())
    ans = sum(cnt[l - 1:r - 1])
    print(ans)

Fixed submission:
N, Q = map(int, input().split())
S = list(input())
cnt = [0] * (N)

for i in range(1, N):
    if S[i - 1] + S[i] == 'AC':
        cnt[i] = cnt[i - 1] + 1
    else:
        cnt[i] = cnt[i - 1]

for _ in range(Q):
    l, r = map(int, input().split())
    ans = cnt[r - 1] - cnt[l - 1]
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    ans = 0
    l, r = map(int, input().split())
    sub = S[l - 1: r]
    print(sub.count('AC'))

Fixed submission:
N, Q = map(int, input().split())
S = list(input())
cnt = [0] * (N)

for i in range(1, N):
    if S[i - 1] + S[i] == 'AC':
        cnt[i] = cnt[i - 1] + 1
    else:
        cnt[i] = cnt[i - 1]

for _ in range(Q):
    l, r = map(int, input().split())
    ans = cnt[r - 1] - cnt[l - 1]
    print(ans)
Buggy python submission (verdict: Runtime Error):
from math import gcd
n = int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, n):
    ans = gcd(ans, a[i])
print(ans)


Fixed submission:
from fractions import gcd

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

ans = a[0]
for i in range(1, n):
    ans = gcd(ans, a[i])

print(ans)

Buggy python submission (verdict: Runtime Error):
import math

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

ans = a[0]
for i in range(1, n):
    ans = math.gcd(ans, a[i])

print(ans)

Fixed submission:
from fractions import gcd

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

ans = a[0]
for i in range(1, n):
    ans = gcd(ans, a[i])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = sum(a)
for i in range(k + 1):
    total = 0
    for ai in a:
        total += ai ^ i
    ans = max(ans, total)
print(ans)


Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
x = 0
for i in range(40, -1, -1):
    c = 0
    for ai in a:
        if (ai >> i) & 1:
            c += 1
    if (n - c) > c and x + (1 << i) <= k:
        x += 1 << i
        ans += (n - c) * (1 << i)
    else:
        ans += c * (1 << i)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
scaffolds = list(map(int, input().split()))
dp = [10 ** 5 * 10 ** 4] * n
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i + j >= n:
            break
        dp[i + j] = min(dp[i + j], abs(scaffolds[i] - scaffolds[i + j]) + dp[i])
print(dp[-1])

Fixed submission:
n, k = map(int, input().split())
scaffolds = list(map(int, input().split()))
dp = [10 ** 5 * 10 ** 4] * n
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i + j >= n:
            break
        dp[i + j] = min(dp[i + j], abs(scaffolds[i] - scaffolds[i + j]) + dp[i])
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
scaffolds = list(map(int, input().split()))
dp = [10 ** 5 * 10 ** 4] * n
dp[0] = 0
for i in range(1, n):
    scaffold = scaffolds[i]
    threshold = max(-1, i - k - 1)
    for j in range(i - 1, threshold, -1):
        dp[i] = min(dp[i], abs(scaffold - scaffolds[j]) + dp[j])
print(dp[-1])

Fixed submission:
n, k = map(int, input().split())
scaffolds = list(map(int, input().split()))
dp = [10 ** 5 * 10 ** 4] * n
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i + j >= n:
            break
        dp[i + j] = min(dp[i + j], abs(scaffolds[i] - scaffolds[i + j]) + dp[i])
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
prefectures = [[] for _ in range(10 ** 5)]

for i in range(m):
    p, y = map(int, input().split())
    prefectures[p].append([y, i])

ans = [''] * m
for p in range(10 ** 5):
    prefecture = prefectures[p]
    prefecture.sort(key=lambda x: x[0])
    for i in range(len(prefecture)):
        ans[prefecture[i][1]] = '{:006}{:006}'.format(p, i + 1)

for i in range(m):
    print(ans[i])


Fixed submission:
n, m = map(int, input().split())
prefectures = [[] for _ in range(10 ** 5)]

for i in range(m):
    p, y = map(int, input().split())
    prefectures[p - 1].append([y, i])

ans = [''] * m
for p in range(10 ** 5):
    prefecture = prefectures[p]
    prefecture.sort(key=lambda x: x[0])
    for i in range(len(prefecture)):
        ans[prefecture[i][1]] = '{:006}{:006}'.format(p + 1, i + 1)

for i in range(m):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

n, m = map(int, input().split())
prefectures = [list(map(int, input().split())) for _ in range(m)]
ID = defaultdict(list)

for prefecture in prefectures:
    p, y = prefecture
    ID[p].append(y)

for k, v in ID.items():
    v.sort()

for prefecture in prefectures:
    p, y = prefecture
    order = ID[p].index(y) + 1
    print('{:006}{:006}'.format(p, order))

Fixed submission:
n, m = map(int, input().split())
prefectures = [[] for _ in range(10 ** 5)]

for i in range(m):
    p, y = map(int, input().split())
    prefectures[p - 1].append([y, i])

ans = [''] * m
for p in range(10 ** 5):
    prefecture = prefectures[p]
    prefecture.sort(key=lambda x: x[0])
    for i in range(len(prefecture)):
        ans[prefecture[i][1]] = '{:006}{:006}'.format(p + 1, i + 1)

for i in range(m):
    print(ans[i])