Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = sorted(sorted(AB, key=lambda x: x[0], reverse=False), key=lambda x: x[1], reverse=True)
x = [0] * M
cnt = 0
cntIN = M
preB = 0
for a, b in AB:
    if preB != b:
        k = M
    i = min(M-a, k)
    while i>=0 and x[i] != 0:
        i -= 1
    else:
        if i >= 0:
            x[i] = b
            k = i - 1
            cntIN -= 1
            if cntIN <= 0:
                break

print(sum(x))


Fixed submission:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = sorted(sorted(AB, key=lambda x: x[0], reverse=False), key=lambda x: x[1], reverse=True)
x = [0] * M
p = [x for x in range(M)]

cnt = 0
cntIN = M
for a, b in AB:
    i = M-a

    s = []
    while i >= 0 and p[i] != i:
        s.append(i)
        i = p[i]
    for j in s:
        p[j] = i - 1

    if i >= 0:
        x[i] = b
        p[i] = i - 1
        cntIN -= 1            
        if cntIN <= 0:
            break

print(sum(x))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = sorted(sorted(AB, key=lambda x: x[0], reverse=True), key=lambda x: x[1], reverse=True)
x = [0] * M
cnt = 0
cntIN = M
for a, b in AB:
    i = M-a
    while i>=0 and x[i] != 0:
        i -= 1
    else:
        if i >= 0:
            x[i] = b
            cntIN -= 1
            if cntIN <= 0:
                break

print(sum(x))


Fixed submission:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = sorted(sorted(AB, key=lambda x: x[0], reverse=False), key=lambda x: x[1], reverse=True)
x = [0] * M
p = [x for x in range(M)]

cnt = 0
cntIN = M
for a, b in AB:
    i = M-a

    s = []
    while i >= 0 and p[i] != i:
        s.append(i)
        i = p[i]
    for j in s:
        p[j] = i - 1

    if i >= 0:
        x[i] = b
        p[i] = i - 1
        cntIN -= 1            
        if cntIN <= 0:
            break

print(sum(x))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = sorted(sorted(AB, key=lambda x: x[0], reverse=True), key=lambda x: x[1], reverse=True)
x = [0] * M
cnt = 0
cntIN = M
for a, b in AB:
    i = M-a
    while i>=0 and x[i] != 0:
        i -= 1
    else:
        if i >= 0:
            x[i] = b
            cntIN -= 1
            if cntIN <= 0:
                break

print(sum(x))


Fixed submission:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = sorted(sorted(AB, key=lambda x: x[0], reverse=False), key=lambda x: x[1], reverse=True)
x = [0] * M
p = [x for x in range(M)]

cnt = 0
cntIN = M
for a, b in AB:
    i = M-a

    s = []
    while i >= 0 and p[i] != i:
        s.append(i)
        i = p[i]
    for j in s:
        p[j] = i - 1

    if i >= 0:
        x[i] = b
        p[i] = i - 1
        cntIN -= 1            
        if cntIN <= 0:
            break

print(sum(x))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]

S = []

cnt = 0
for i in range(N):
    j = bisect.bisect_left(S, A[i])
    if j <= 0:
        cnt += 1
        S.insert(j, A[i])
    else:
        S[j-1] = A[i]

print(cnt)


Fixed submission:
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]

S = [0] * N

end = N
for i in range(N):
    j = bisect.bisect_left(S, A[i], end, N)
    if j <= end:
        S[j-1] = A[i]
        end -= 1
    else:
        S[j-1] = A[i]

print(N-end)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]

S = []

cnt = 0
for i in range(N):
    j = bisect.bisect_left(S, A[i])
    if j <= 0:
        cnt += 1
        S.insert(j, A[i])
    else:
        S[j-1] = A[i]

print(cnt)


Fixed submission:
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]

S = [0] * N

end = N
for i in range(N):
    j = bisect.bisect_left(S, A[i], end, N)
    if j <= end:
        S[j-1] = A[i]
        end -= 1
    else:
        S[j-1] = A[i]

print(N-end)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
S = sum(A)
ans = [0] * N
for i in range(N):
    x = 1
    for j in range(N):
        if x == 1:
            ans[i] += A[(i+j)%N]
        else:
            ans[i] -= A[(i+j)%N]
        x ^= 1


print(" ".join(map(str, ans)))


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
S = sum(A)
ans = [0] * N
x = 1
for j in range(N):
    if x == 1:
        ans[0] += A[j%N]
    else:
        ans[0] -= A[j%N]
    x ^= 1

for i in range(N-1):
    ans[i+1] = (A[i] - ans[i] // 2) * 2

print(" ".join(map(str, ans)))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
S = sum(A)
ans = [0] * N
for i in range(N):
    x = 1
    for j in range(N):
        if x == 1:
            ans[i] += A[(i+j)%N]
        else:
            ans[i] -= A[(i+j)%N]
        x ^= 1


print(" ".join(map(str, ans)))


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
S = sum(A)
ans = [0] * N
x = 1
for j in range(N):
    if x == 1:
        ans[0] += A[j%N]
    else:
        ans[0] -= A[j%N]
    x ^= 1

for i in range(N-1):
    ans[i+1] = (A[i] - ans[i] // 2) * 2

print(" ".join(map(str, ans)))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import chain


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

edges = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    edges[u].append(v)

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

def find_next(pos, e):
    c1 = e[pos]
    c2 = chain.from_iterable([e[c]for c in c1])
    return list(chain.from_iterable([e[c] for c in c2]))

visited = [0 for _ in range(n + 1)]
cost = 0
st = deque([(s, 0)])
ans = -1
pre = None
while len(st):
    pos, cost = st.popleft()
    if pos == t:
        ans = cost
        break
    for n in find_next(pos, edges):
        if visited[n] == 0:
            st.append((n, cost + 1))
            visited[n] = 1

print(ans)

Fixed submission:
import sys
N, M = map(int, input().split())

class Bridge:
    def __init__(self, nodeA, nodeB):
        self.edges = [BridgeEdge(nodeA, self), BridgeEdge(nodeB, self)]
        nodeA.addEdge(self.edges[1])
        #nodeB.addEdge(self.edges[0])

class BridgeEdge:
    def __init__(self, node, edge):
        self.edge = edge
        self.node = node
        self.flag = 0

class Node:
    def __init__(self, id):
        self.id = id
        self.bridges = []
    def addEdge(self, bridgeEdge):
        self.bridges.append(bridgeEdge)
    def __repr__(self):
        return "({})".format(self.id)

nodes = [Node(i) for i in range(N+1)]

for ui, vi in (map(int, input().split()) for _ in range(M)):
    Bridge(nodes[ui], nodes[vi])

S, T = map(int, input().split())

#nodes[S].flag = 1
s = [(None, nodes[S], 0)]
idx = 0
isOK = False
while idx < len(s):
    pre, cur, level = s[idx]
    idx += 1
    nxtlevel = level + 1
    nxtflag = 1 << (nxtlevel % 3)

    for nxt in cur.bridges:
        if (nxt.flag & nxtflag) == 0:
            nxt.flag |= nxtflag 
            if nxt.node is nodes[T] and nxtflag == 1:
                isOK = True
                break
            s.append((cur, nxt.node, nxtlevel))
    else:
        continue
    break
if isOK:
    print(nxtlevel//3)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def opt(a, b):
    c = gcd(a, b)
    return a//c, b//c

def dot(A, B):
    a = A[0] * B[0]
    b = A[1] * B[1]
    return opt(a, b)

def add(A, B):
    return opt(A[0]*B[1] + B[0]*A[1], A[1] * B[1])

N, A, B, C = map(int, input().split())

A = opt(A, 100)
B = opt(B, 100)
C = opt(C, 100)

g = 1000000007

c = [((1, 1), 0, 0, 0)]
ans = (0, 1)
e = (0, 1)
pi = 0
while pi < len(c):

    PQ, cnt, acnt, bcnt = c[pi]
    pi += 1

    if e[1] > (e[1] - e[0]) * g * 100:
        continue
    if acnt >= N or bcnt >= N:
        e = add(e, PQ)
        ans = add(ans, opt(cnt * PQ[0], PQ[1]))
        continue

    cnt += 1
    c.append((dot(PQ, A), cnt, acnt+1, bcnt))
    c.append((dot(PQ, B), cnt, acnt, bcnt+1))
    c.append((dot(PQ, C), cnt, acnt, bcnt))


print(ans[0] * pow(ans[1], g-2,g)%g)



Fixed submission:
N = int(input())
print("{:.0f}".format((180 -  360 / N) * N))
Buggy python submission (verdict: Time Limit Exceeded):
import math

g = 1000000007
N, A, B, C = map(int, input().split())


fr = [1] * (2 * N)
for i in range(2, 2*N):
    fr[i] = i * fr[i-1] % g

def dot(A, B):
    return A * B % g

def po(A, B):

    return pow(A, B, g)

def add(A, B):
    return (A + B) % g

def combi(a, b):
    return fr[a] * div(1, fr[b]) * div(1, fr[a-b]) % g

def div(a, b):
    return a * pow(b, g-2, g) % g



AB = A+B
A = div(A, AB)
B = div(B, AB)
C = div(C, 100)


s = 0
for M in range(N, 2 * N):
    w = dot(add(dot(po(A, N), po(B, M - N)), dot(po(A, M-N), po(B, N))), combi(M-1, N-1) * M * div(1, add(1, -C)))
    s = add(s, w)

print(s)


Fixed submission:
import math

g = 1000000007
N, A, B, C = map(int, input().split())


fr = [1] * (2 * N)
for i in range(2, 2*N):
    fr[i] = i * fr[i-1] % g

def dot(A, B):
    return A * B % g

def po(A, B):

    return pow(A, B, g)

def add(A, B):
    return (A + B) % g

def combi(a, b):
    return fr[a] * div(1, fr[b]) * div(1, fr[a-b]) % g

def div(a, b):
    return a * pow(b, g-2, g) % g



AB = A+B
A = div(A, AB)
B = div(B, AB)
C = div(C, 100)


s = 0
for M in range(N, 2 * N):
    w = dot(add(dot(po(A, N), po(B, M - N)), dot(po(A, M-N), po(B, N))), combi(M-1, N-1) * M * div(1, add(1, -C)))
    s = add(s, w)

print(s)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

g = 1000003
for x, d, n in (map(int, input().split()) for _ in range(N)):
    ans = 1

    for _ in range(n):
        ans = ans * x % g
        x += d

    print(ans)


Fixed submission:
import math
N = int(input())

g = 1000003

fr = [1] * g
for x in range(2, g):
    fr[x] = x * fr[x-1] % g

def div(a, b):
    return a * pow(b, g-2, g) % g

for x, d, n in (map(int, input().split()) for _ in range(N)):
    ans = 1

    if d == 0:
        print(pow(x, n, g))

    else:
        s = div(x, d)
        x, y = s+n-1, s-1
        if s+n-1 < g :
            print(div(fr[x], fr[y]) * pow(d, n, g) % g)
        else:
            print(0)
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = sorted((map(lambda y: (y[0], -int(y[1]), x), input().split()) for x in range(1, N+1)))
for x in S:
  print(x[2])


Fixed submission:
N = int(input())
SP = [[x+1] + list(input().split()) for x in range(N)]

SP2 = sorted(sorted(SP, key=lambda x:int(x[2]), reverse=True), key=lambda x:x[1])

for i in range(N):
    print(SP2[i][0])
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

allL = 1
allR = N
for L, R in map(int, input().split()) in range(M):
  allL = max(allL, L)
  allR = min(allR, R)

print(max(allR - allL + 1, 0))


Fixed submission:
N, M = map(int, input().split())

allL = 1
allR = N
for L, R in (map(int, input().split()) for _ in range(M)):
  allL = max(allL, L)
  allR = min(allR, R)

print(max(allR - allL + 1, 0))
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = sorted(map(int, input().split()))
BC = sorted([ list(map(int, input().split())) for _ in range(M)], key=lambda x:x[1], reverse=True)

s = 0
i = 0
B = 0
for a in A:
  if B == 0:
    if i < len(BC):
      B, C = BC[i]
      i += 1

  if B > 0 and C > a:
    s += C
    B -= 1
  else
    s += a

print(s)


Fixed submission:
N, M = map(int, input().split())
A = sorted(map(int, input().split()))
BC = sorted([ list(map(int, input().split())) for _ in range(M)], key=lambda x:x[1], reverse=True)

s = 0
i = 0
B = 0
for a in A:
  if B == 0:
    if i < len(BC):
      B, C = BC[i]
      i += 1

  if B > 0 and C > a:
    s += C
    B -= 1
  else:
    s += a

print(s)
Buggy python submission (verdict: Time Limit Exceeded):
import collections
N = int(input())

P = [0] * N
uvw1 = []
for i in range(1, N):
    u, v, w = map(int, input().split())
    uvw1.append((u, v, 0 if w % 2 == 0 else 1 ))

d = {}
uvw = collections.deque()
for x in sorted(uvw1):
    uvw.append(x)

u, v, w = uvw[0]
d[u] = 0

while len(uvw):
    u, v, w = uvw.popleft()
    if d.get(u, -1) >= 0:
        d[v] = d[u] ^ w
        continue
    elif d.get(v, -1) >= 0:
        d[u] = d[v] ^ w
        continue
    uvw.append((u, v, w))

for i in range(1, N+1):
    print(d[i])


Fixed submission:
import collections
N = int(input())

g = [dict() for _ in range(N+1)]
for i in range(1, N):
    u, v, w = map(int, input().split())
    w = 0 if w % 2 == 0 else 1
    g[u][v] = w
    g[v][u] = w

ret = {1:0}
q = collections.deque()
q.append(1)
while len(q):
    d = q.pop()
    for h in g[d]:
        if ret.get(h, -1) < 0:
            ret[h] = ret[d] ^ g[d][h]
            q.append(h)

for i in range(1, N+1):
    print(ret[i])

Buggy python submission (verdict: Time Limit Exceeded):
import collections
N = int(input())

P = [0] * N
uvw = collections.deque()
for i in range(1, N):
    u, v, w = map(int, input().split())
    uvw.append((u, v, 0 if w % 2 == 0 else 1 ))

d = {}
u, v, w = uvw[0]
d[u] = 0

while len(uvw):
    u, v, w = uvw.popleft()
    if d.get(u, -1) >= 0:
        d[v] = d[u] ^ w
        continue
    elif d.get(v, -1) >= 0:
        d[u] = d[v] ^ w
        continue
    uvw.append((u, v, w))

for i in range(1, N+1):
    print(d[i])

Fixed submission:
import collections
N = int(input())

g = [dict() for _ in range(N+1)]
for i in range(1, N):
    u, v, w = map(int, input().split())
    w = 0 if w % 2 == 0 else 1
    g[u][v] = w
    g[v][u] = w

ret = {1:0}
q = collections.deque()
q.append(1)
while len(q):
    d = q.pop()
    for h in g[d]:
        if ret.get(h, -1) < 0:
            ret[h] = ret[d] ^ g[d][h]
            q.append(h)

for i in range(1, N+1):
    print(ret[i])
Buggy python submission (verdict: Runtime Error):
x = map(int, input().split())
x = x[0], x[2], x[1]
print("Yes" if all(map(lambda x, y: x==y, x, sorted(x))) else "No")


Fixed submission:
import sys
import math
N = list(map(int, input().split()))

t = False
if (N[0] < N[1]) == (N[0] < N[2]):
    if abs(N[1] - N[0]) > abs(N[2] - N[0]):
        t = True

print("Yes" if t else "No")

Buggy python submission (verdict: Runtime Error):
x = input().split()
x = x[0], x[2], x[1]
print("yes" all(map(lambda x, y: x==y, x, sorted(x))) else "No")

Fixed submission:
import sys
import math
N = list(map(int, input().split()))

t = False
if (N[0] < N[1]) == (N[0] < N[2]):
    if abs(N[1] - N[0]) > abs(N[2] - N[0]):
        t = True

print("Yes" if t else "No")
Buggy python submission (verdict: Runtime Error):
input()
s = list(input())
print("".join(("*" if x != y else x for x in s[int(input())] for y in s )))

Fixed submission:
import re
N = int(input())
S = input()
K = int(input())

w = S[K-1]
print(re.sub("[^#]", "*", S.replace(w, "#")).replace("#", w))
Buggy python submission (verdict: Runtime Error):
N,Q=map(int,input().split())
S=input()

lis = [0] * len(S)
for i in range(len(S)):

  if i>0:
    lis[i] += lis[i-1]
  if i < len(S)-1 and S[i] == 'A' and S[i+1] == 'C':
    lis[i+1] += 1


for _ in range(Q):
  L = tuple(map(int, input().split()))

  c = 0
  print(lis[L[1]-1]-lis[L[0]-1])


Fixed submission:
T='ATCG'
print(T[T.find(input())^1])
Buggy python submission (verdict: Runtime Error):
N,Q=map(int,input().split())
S=input()
L=[tuple(map(int, input().split())) for _ in range(Q)]
print("\n".join([str(len(S[nS-1:nE])-len(S[nS-1:nE].replace("AC", "|"))) for nS, nE in L]))


Fixed submission:
S=input()

c=m=0
for x in S:
  #print((m,c,x,"ACGT".find(x)))
  if "ACGT".find(x)>=0:
    c+=1
    m = max(m, c)
  else:
    c = 0

print(m)
Buggy python submission (verdict: Runtime Error):
c = [1]*("z".encode()-"a".encode()+1)
for x in map(lambda x: x-"a".encode(), input().encode()):
	c[x] += 1

m = 1
for x in c:
  m *= c

print(m-1)


Fixed submission:
N = input()
c = [1]*("z".encode()[0]-"a".encode()[0]+1)
for x in map(lambda x: x-"a".encode()[0], input().encode()):
	c[x] += 1

m = 1
for x in c:
  m = (m * x) % (1e9+7)

print("{:.0f}".format(m-1))
Buggy python submission (verdict: Runtime Error):
A, B=map(int, input())
print(A+B if B%A==0 else B-A)

Fixed submission:
A, B=map(int, input().split())
print(A+B if B%A==0 else B-A)
Buggy python submission (verdict: Runtime Error):
T,X = map(input().split())
print(T/X)

Fixed submission:
T,X = map(int, input().split())
print(T/X)
Buggy python submission (verdict: Runtime Error):
N = input()
H = map(int, input().split())

Hk = set()
for h in H:
  Hk.add(h)

def po(h, s, e):
  if h >= Hk[-1]:
    return 1
  posS = s
  hit = False
  cnt = 0
  for posE in range(s, e+1):
    if posE >= e or H[posE] <= Hk[h]:
      hit or= (posE < e)
	if posS < posE:
      cnt += po(h+1, posS, posE)
  if hit:
    cnt += 1
  return cnt



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

Hk = set([0])
for h in H:
  Hk.add(h)
Hk = sorted(Hk)

def po(h, s, e):
  if h >= len(Hk)-1:
    return Hk[h] - Hk[h-1]
  posS = s
  cnt = 0
  for posE in range(s, e+1):
    if posE >= e or H[posE] <= Hk[h]:
      if posS < posE:
        cnt += po(h+1, posS, posE)
      posS = posE + 1
  if h > 0:
    cnt += Hk[h] - Hk[h-1]
  return cnt

print(po(0, 0, len(H)))
Buggy python submission (verdict: Runtime Error):
S = input()
key = "keyence"
for i in range(len(key)+1):
  if S.find(key[:i]) == 0 and s.find(key[i:], len(S)-i) == len(S) - i:
    print("Yes")
    break
else:
  print("No")


Fixed submission:
S = input()
key = "keyence"
for i in range(len(key)+1):
  if key == S[:i] + S[len(S)-len(key)+i:]:
    print("YES")
    break
else:
  print("NO")
Buggy python submission (verdict: Runtime Error):
N = int(input())
H = list(map(int, input().split()))
P = [-1] * len(H)

def minv(i, v):
  if i < len(H):
    if P[i] < 0:
      P[i] = v
    else:
      P[i] = min(P[i], v)

for i in range(len(H)-1):
  minv(i + 1, H[i] + abs(H[i] - H[i+1]))
  minv(i + 2, H[i] + abs(H[i] - H[i+2]))

print(H[-1])

Fixed submission:
N = int(input())
H = list(map(int, input().split()))
P = [0] + [-1] * (len(H)-1)

def minv(i, v):
  if i < len(H):
    cost = v()
    if P[i] < 0:
      P[i] = cost
    else:
      P[i] = min(P[i], cost)

for i in range(len(H)-1):
  minv(i + 1, lambda : P[i] + abs(H[i] - H[i+1]))
  minv(i + 2, lambda : P[i] + abs(H[i] - H[i+2]))

print(P[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = list(map(int, input().split()))
P = [0] + [-1] * (len(H)-1)

def minv(i, v):
  if i < len(H):
    cost = v()
    if P[i] < 0:
      P[i] = cost
    else:
      P[i] = min(P[i], cost)

for i in range(len(H)-1):
  for k in range(1, K+1):
    minv(i + k, lambda : P[i] + abs(H[i] - H[i+k]))

print(P[-1])

Fixed submission:
N, K = map(int, input().split())
H = list(map(int, input().split()))
P = [0] + [-1] * (len(H)-1)

def minv(i, v):
  if i < len(H):
    cost = v()
    if P[i] < 0:
      P[i] = cost
    else:
      P[i] = min(P[i], cost)

for i in range(len(H)-1):
  for k in range(1, K+1):
    minv(i + k, lambda : P[i] + abs(H[i] - H[i+k]))

print(P[-1])

Buggy python submission (verdict: Runtime Error):
N, K = int(input())
H = list(map(int, input().split()))
P = [0] + [-1] * (len(H)-1)

def minv(i, v):
  if i < len(H):
    cost = v()
    if P[i] < 0:
      P[i] = cost
    else:
      P[i] = min(P[i], cost)

for i in range(len(H)-1):
  for k in range(1, K+1):
    minv(i + k, lambda : P[i] + abs(H[i] - H[i+k]))

print(P[-1])


Fixed submission:
N, K = map(int, input().split())
H = list(map(int, input().split()))
P = [0] + [-1] * (len(H)-1)

def minv(i, v):
  if i < len(H):
    cost = v()
    if P[i] < 0:
      P[i] = cost
    else:
      P[i] = min(P[i], cost)

for i in range(len(H)-1):
  for k in range(1, K+1):
    minv(i + k, lambda : P[i] + abs(H[i] - H[i+k]))

print(P[-1])

Buggy python submission (verdict: Runtime Error):
N, K = int(input())
H = list(map(int, input().split()))
P = [0] + [-1] * (len(H)-1)

def minv(i, v):
  if i < len(H):
    cost = v()
    if P[i] < 0:
      P[i] = cost
    else:
      P[i] = min(P[i], cost)

for i in range(len(H)-1):
  for k in range(1, K+1):
    minv(i + 1, lambda : P[i] + abs(H[i] - H[i+k]))

print(P[-1])


Fixed submission:
N, K = map(int, input().split())
H = list(map(int, input().split()))
P = [0] + [-1] * (len(H)-1)

def minv(i, v):
  if i < len(H):
    cost = v()
    if P[i] < 0:
      P[i] = cost
    else:
      P[i] = min(P[i], cost)

for i in range(len(H)-1):
  for k in range(1, K+1):
    minv(i + k, lambda : P[i] + abs(H[i] - H[i+k]))

print(P[-1])
Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())

DP = [-1] * (W+1)
DP[W] = 0

def maxv(i, v):
    if i >= 0:
        if v > DP[i]:
            DP[i] = v

for w, v in (map(int, input().split()) for _ in range(N)):
    for i in range(1, W+1):
        if DP[i] >= 0:
            maxv(i-w, DP[i]+v)
            maxv(0, DP[i-w])

print(DP[0])


Fixed submission:
N = int(input())
wa, wb, wc = [0] * 3
for a, b, c in (map(int, input().split()) for _ in range(N)):
  wa, wb, wc = a + max(wb, wc), b + max(wa, wc), c + max(wa, wb)
print(max(wa, wb, wc))
Buggy python submission (verdict: Runtime Error):
import heapq

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

h = []
for _ in range(n):
    heapq.heappush(h, int(input()))

q = [heapq.heappop(h) for _ in range(k-1)]

ans = 1e9
while len(h):
    p = i % (k-1)
    s = q[p]
    e = heapq.heappop(h)
    q[p] = e
    ans = min(ans, e - s)

print(ans)


Fixed submission:
import heapq

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

h = []
for _ in range(n):
    heapq.heappush(h, int(input()))

q = [heapq.heappop(h) for _ in range(k-1)]

ans = 1e9
for i in range(len(h)):
    p = i % (k-1)
    s = q[p]
    e = heapq.heappop(h)
    q[p] = e
    ans = min(ans, e - s)

print(ans)
Buggy python submission (verdict: Runtime Error):
N = input()
Nlen = len(N)
N = int(N)

def f(i, n, T, F, S):
  if i >= Nlen:
    return 1 if n <= N and T > 0 and F > 0 and S > 0 else 0
  n *= 10
  cnt = 0
  if n == 0:
    cnt += f(i+1, n, T  , F  , S  )
  cnt += f(i+1, n+3, T+1, F  , S  )
  cnt += f(i+1, n+5, T  , F+1, S  )
  cnt += f(i+1, n+7, T  , F  , S+1)

print(f(0, 0, 0, 0, 0))


Fixed submission:
N = input()
Nlen = len(N)
N = int(N)

def f(i, n, T, F, S):
  if i >= Nlen:
    return 1 if n <= N and T > 0 and F > 0 and S > 0 else 0
  n *= 10
  cnt = 0
  if n == 0:
    cnt += f(i+1, n, T  , F  , S  )
  cnt += f(i+1, n+3, T+1, F  , S  )
  cnt += f(i+1, n+5, T  , F+1, S  )
  cnt += f(i+1, n+7, T  , F  , S+1)
  return cnt

print(f(0, 0, 0, 0, 0))
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(N)]

PY = sorted(PY)

keyP = -1
for P, Y in PY:
  if keyP != P:
    keyP = P
    keyNo = 1

  print("{:0>6}{:0>6}", keyP, keyNo)
  keyNo += 1


Fixed submission:
N, M = map(int, input().split())
PY = [list(map(int, input().split() +[x])) for x in range(M)]

PY = sorted(PY)

keyP = -1
for i, (P, Y, _) in enumerate(PY):
  if keyP != P:
    keyP = P
    keyNo = 1

  PY[i].append("{:0>6}{:0>6}".format(keyP, keyNo))
  keyNo += 1

for P, Y, _, s in sorted(PY, key=lambda x:x[2]):
  print(s)
Buggy python submission (verdict: Runtime Error):
S = sorted(input(), reverse=False)
print(int(S[0:2])+int(S[2]))


Fixed submission:
S = "".join(sorted(input().split(), reverse=True))
print(int(S[0:2])+int(S[2]))
Buggy python submission (verdict: Runtime Error):
S = input()
T = input()

U = set()
for s, t in sorted(zip(S, T)):
  U.add((s, t))

for x, y in zip(U[0:-1], U[1:]):
  if x == y:
    print("No")
    break
else:
  print("Yes")

  



Fixed submission:
S = input()
T = input()
TS = list(zip(T, S))

TS_set = set()
for t,s in TS:
  TS_set.add((t,s))

S_set = set()
for x in TS_set:
  S_set.add(x[1])

T_set = set()
for x in TS_set:
  T_set.add(x[0])

print("Yes" if S == T or len(TS_set) == len(S_set) == len(T_set) else "No")