Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
mod=10**9+7
def f(a,r):
    s=[[0,0],[0,0]]
    s[0][0]=(a[0][0]*r[0][0]+a[0][1]*r[1][0])%mod
    s[0][1]=(a[0][0]*r[0][1]+a[0][1]*r[1][1])%mod
    s[1][0]=(a[1][0]*r[0][0]+a[1][1]*r[1][0])%mod
    s[1][1]=(a[1][0]*r[0][1]+a[1][1]*r[1][1])%mod
    return s
b=[[1,1],[1,0]]
k=[b]
for i in range(20):
    k.append(f(k[-1],k[-1]))
n,m=map(int,input().split())
t=0
ans=1
for i in range(m):
    a=int(input())
    if t==a:
        print(0)
        break
    else:
        s=bin(a-1-t)[2:]
        s="0"*(21-len(s))+s
        s=s[::-1]
        p=[[1,0],[0,1]]
        for j in range(21):
            if s[j]=="1":
                p=f(p,k[j])
        ans=(ans*p[0][0])%mod
        t=a+1
        if i==m-1:
            s=bin(n-t)[2:]
            s="0"*(21-len(s))+s
            s=s[::-1]
            p=[[1,0],[0,1]]
            for j in range(21):
                if s[j]=="1":
                    p=f(p,k[j])
            ans=(ans*p[0][0])%mod
else:
    print(ans)

Fixed submission:
a=list(map(int,input().split()));print(sum(a)-max(a))
Buggy python submission (verdict: Runtime Error):
import numpy as np
a=np.array([[0 if i!="." else 1 for i in input()]for j in range(h)])
s,t,u,p=np.zeros((h,w)),np.zeros((h,w)),np.zeros((h,w)),np.zeros((h,w))
for i in range(h):
    s[i]=(s[i-1]+1)*a[i]
    t[-i-1]=(t[-i]+1)*a[-i-1]
for i in range(w):
    u[:,j]=(u[:,j-1]+1)*a[:,j]
    p[:,-j-1]=(p[:,-j]+1)*a[:,-j-1]
print(np.max(s+t+u+p)-3)

Fixed submission:
import numpy as np
h,w=map(int,input().split())
a=np.array([[0 if i!="." else 1 for i in input()]for j in range(h)])
s,t,u,p=np.zeros((h,w)),np.zeros((h,w)),np.zeros((h,w)),np.zeros((h,w))
for i in range(h):
    s[i]=(s[i-1]+1)*a[i]
    t[-i-1]=(t[-i]+1)*a[-i-1]
for i in range(w):
    u[:,i]=(u[:,i-1]+1)*a[:,i]
    p[:,-i-1]=(p[:,-i]+1)*a[:,-i-1]
print(int(np.max(s+t+u+p))-3)

Buggy python submission (verdict: Time Limit Exceeded):
h,w=map(int,input().split())
t=[["#"]*(w+2)]+[list("#"+input()+"#")for i in range(h)]+[["#"]*(w+2)]
p=[[[0,0]for i in range(w+2)] for i in range(h+2)]
def  f(a,b,c):
    d=0
    if c=="h":
        while t[a][b]==".":
            a+=1
            d+=1
    else:
        while t[a][b]==".":
            b+=1
            d+=1
    return d
a=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if t[i][j]!="#":
            if p[i-1][j][0]==0:
                p[i][j][0]=f(i,j,"h")
            else:
                p[i][j][0]=p[i-1][j][0]
            if p[i][j-1][1]==0:
                p[i][j][1]=f(i,j,"w")
            else:
                p[i][j][1]=p[i][j-1][1]
            a=max(a,sum(p[i][j]))
print(a-1)        

Fixed submission:
import numpy as np
h,w=map(int,input().split())
a=np.array([[0 if i!="." else 1 for i in input()]for j in range(h)])
s,t,u,p=np.zeros((h,w)),np.zeros((h,w)),np.zeros((h,w)),np.zeros((h,w))
for i in range(h):
    s[i]=(s[i-1]+1)*a[i]
    t[-i-1]=(t[-i]+1)*a[-i-1]
for i in range(w):
    u[:,i]=(u[:,i-1]+1)*a[:,i]
    p[:,-i-1]=(p[:,-i]+1)*a[:,-i-1]
print(int(np.max(s+t+u+p))-3)
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
a=list(map(int,input().split()))
g=0
for i in range(0,min(n,k)):
    for j in range(0,min(k-i,n-i)):
        s=sorted(a[:i]+a[n-j:])
        p=sum(s)
        t=i+j
        c=0
        while len(s)>=c+1 and t+1<=k:
            if s[c]<0:
                p-=s[c]
                c+=1
                t+=1
            else:
                break
        g=max(g,p)
print(g)

Fixed submission:
a,p=map(int,input().split());print((3*a+p)//2)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    b,c=map(int,input().split())
    a+=[c]*b
a=sorted(a)
print(sum(a[-n:]))

Fixed submission:
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))[::-1]
k=sorted([list(map(int,input().split()))for i in range(m)],key=lambda x:-x[1])+[[0,0]]
c,d=0,0
t=0
ans=0
while c<n:
    if a[d]>=k[t][1]:
        ans+=a[d]
        d+=1
        c+=1
    else:
        ans+=k[t][1]*min(n-c,k[t][0])
        c+=k[t][0]
        t+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left as bl
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
for i in range(m):
    b,c=map(int,input().split())
    t=bl(a,c)
    if t<=b:
        a=[c]*t+a[t:]
    else:
        a=a[b:t]+[c]*b+a[t:]
print(sum(a))

Fixed submission:
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))[::-1]
k=sorted([list(map(int,input().split()))for i in range(m)],key=lambda x:-x[1])+[[0,0]]
c,d=0,0
t=0
ans=0
while c<n:
    if a[d]>=k[t][1]:
        ans+=a[d]
        d+=1
        c+=1
    else:
        ans+=k[t][1]*min(n-c,k[t][0])
        c+=k[t][0]
        t+=1
print(ans)

Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left as bl
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
for i in range(m):
    b,c=map(int,input().split())
    t=bl(a,c)
    print(a)
    if t<=b:
        a=[c]*t+a[t:]
    else:
        a=a[b:t]+[c]*b+a[t:]
print(sum(a))

Fixed submission:
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))[::-1]
k=sorted([list(map(int,input().split()))for i in range(m)],key=lambda x:-x[1])+[[0,0]]
c,d=0,0
t=0
ans=0
while c<n:
    if a[d]>=k[t][1]:
        ans+=a[d]
        d+=1
        c+=1
    else:
        ans+=k[t][1]*min(n-c,k[t][0])
        c+=k[t][0]
        t+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
m,k=map(int,input().split())
if 0<=k<2**m:
    if m==1 and k==1:
        print(-1)
    else:
        s=[i for i in range(2**m) if i!=k]
        print(*s,k,*s[::-1],k)
else:
    print(-1)

Fixed submission:
m,k=map(int,input().split())
if 0<=k<2**m:
    if m==1:
        if k==1:print(-1)
        else:print(*[1,1,0,0])
    else:
        s=[str(i) for i in range(2**m) if i!=k]
        c=""
        for i in s:c+=i+" "
        c+=str(k)+" "
        for i in s[::-1]:c+=i+" "
        print(c+str(k))
else:
    print(-1)

Buggy python submission (verdict: Runtime Error):
m,k=map(int,input().split())
if 0<=k<2**m:
    s=[i for i in range(2**m) if i!=k]
    print(*s,k,*s[::-1],k)
else:
    print(-1)

Fixed submission:
m,k=map(int,input().split())
if 0<=k<2**m:
    if m==1:
        if k==1:print(-1)
        else:print(*[1,1,0,0])
    else:
        s=[str(i) for i in range(2**m) if i!=k]
        c=""
        for i in s:c+=i+" "
        c+=str(k)+" "
        for i in s[::-1]:c+=i+" "
        print(c+str(k))
else:
    print(-1)

Buggy python submission (verdict: Runtime Error):
m,k=map(int,input().split())
if 0<=k<2**m:
    s=[i for i in range(2**m) if i!=k]
    print(*s,k,*s[::-1],k)
else:
    print(-1)

Fixed submission:
m,k=map(int,input().split())
if 0<=k<2**m:
    if m==1:
        if k==1:print(-1)
        else:print(*[1,1,0,0])
    else:
        s=[str(i) for i in range(2**m) if i!=k]
        c=""
        for i in s:c+=i+" "
        c+=str(k)+" "
        for i in s[::-1]:c+=i+" "
        print(c+str(k))
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
s=input()+"d"
d=[]
r=s[0]
c=0
for i in range(n+1):
    if r==s[i]:
        c+=1
    else:
        d.append(c)
        r=s[i]
        c=1
if s[0]=="0":
        d=[0]+d
if s[-2]=="0":
    d+=[0]
if len(d)<=2*k+1:
    print(n)
else:
    l=sum(d[:2*k+1])
    p=sum(d[:2*k+1])
    for i in range(len(d)-2*k-3):
        p=p-d[2*i]-d[2*i+1]+d[2*i+2*k+1]+d[2*i+2*k+2]
        l=max(l,p)
    print(l)

Fixed submission:
n,k=map(int,input().split())
s=input()+"d"
d=[]
r=s[0]
c=0
for i in range(n+1):
    if r==s[i]:
        c+=1
    else:
        d.append(c)
        r=s[i]
        c=1
if s[0]=="0":
        d=[0]+d
if s[-2]=="0":
    d+=[0]
if len(d)<=2*k+1:
    print(n)
else:
    l=sum(d[:2*k+1])
    p=sum(d[:2*k+1])
    for i in range((len(d)-2*k-1)//2):
        p=p-d[2*i]-d[2*i+1]+d[2*i+2*k+1]+d[2*i+2*k+2]
        l=max(l,p)
    print(l)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left as bi
x,y,z,k=map(int,input().split())
a=sorted(list(map(int,input().split())))[::-1]
b=sorted(list(map(int,input().split())))[::-1]
c=sorted(list(map(int,input().split())))[::-1]
for i in sorted([j+i for j in c for i in sorted([i+j for i in a for j in b])[::-1][:k]])[::-1][:k]:
    print(i)

Fixed submission:
x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
b=list(map(int,input().split()))
b.sort(reverse=True)
c=list(map(int,input().split()))
c.sort(reverse=True)
d=[i+j for i in a for j in b]
d.sort(reverse=True)
e=[i+j for i in c for j in d[:k]]
e.sort(reverse=True)
for i in range(k):
    print(e[i])
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n,q=map(int,input().split())
s=input()
e=[[0]*n for i in range(26)]
p=n
for i in range(n):
    e[ord(s[i])-ord("A")][i]+=1
h=np.array([1]*n)
for i in range(q):
    t,d=map(str,input().split())
    if d=="R":
        l=h*np.array(e[ord(t)-ord("A")])
        p-=l[-1]
        h=h-np.array(l)+np.array(np.hstack([[0], l[:-1]]))
    else:
        l=h*np.array(e[ord(t)-ord("A")])
        p-=l[0]
        h=h-np.array(l)+np.array(np.hstack([l[1:],[0]]))
print(p)

Fixed submission:
n,q=map(int,input().split())
s="0"+input()+"0"
a=[list(input().split())for i in range(q)]
l=0
r=n+1
for i in range(q-1,-1,-1):
    t,d=a[i]
    if t==s[l] and d=="R":
        l-=1
    elif t==s[l+1] and d=="L":
        l+=1
    if t==s[r] and d=="L":
        r+=1
    elif t==s[r-1] and d=="R":
        r-=1
print(max(0,r-l-1))
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=[[]for i in range(n+1)]
d=[1]
s[int(input())].append(0)
for i in range(1,n):
    j=int(input())
    t=0
    s[j].append(i)
    if len(s[j])>1:
        if s[j][-2]!=s[j][-1]-1:
            t+=d[i-1]+d[s[j][-2]]
        else:
            t+=d[i-1]
    else: 
        t+=d[i-1]
    d.append(t)
print(d[-1]%(10**9+7))   

Fixed submission:
n=int(input())
s=[[]for i in range(2*10**5+1)]
d=[1]
s[int(input())].append(0)
for i in range(1,n):
    j=int(input())
    t=0
    s[j].append(i)
    if len(s[j])>1:
        if s[j][-2]!=s[j][-1]-1:
            t+=d[i-1]+d[s[j][-2]]
        else:
            t+=d[i-1]
    else: 
        t+=d[i-1]
    d.append(t)
print(d[-1]%(10**9+7))

Buggy python submission (verdict: Runtime Error):
n=int(input())
s=[[]for i in range(n+1)]
d=[1]
s[int(input())].append(0)
for i in range(1,n):
    j=int(input())
    t=0
    s[j].append(i)
    if len(s[j])>1:
        if s[j][-2]!=s[j][-1]-1:
            t+=d[i-1]+d[s[j][-2]]
        else:
            t+=d[i-1]
    else: 
        t+=d[i-1]
    d.append(t)
print(d[-1]%(10**9+7))   

Fixed submission:
n=int(input())
s=[[]for i in range(2*10**5+1)]
d=[1]
s[int(input())].append(0)
for i in range(1,n):
    j=int(input())
    t=0
    s[j].append(i)
    if len(s[j])>1:
        if s[j][-2]!=s[j][-1]-1:
            t+=d[i-1]+d[s[j][-2]]
        else:
            t+=d[i-1]
    else: 
        t+=d[i-1]
    d.append(t)
print(d[-1]%(10**9+7))
Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
s=[2**i for i in range(38)]
d=[0]*38
i=1
if ((b+1)//2-a//2)%2==1:
    d[0]+=1
while i<39:
    if s[i]>b:
        break
    elif s[i]>a: 
        a=s[i]
    p,q=a%s[i],a//s[i]
    o,t=b%s[i],b//s[i]
    if q==t:
        if q%2==1:
            if (b-a+1)%2==1:
                d[i]=1
    else:
        h=0
        if q%2==1:
            h+=(q+1)*s[i]-a  
        if t%2==1:
            h+=b-t*s[i]+1
        if h%2==1:
            d[i]=1
    i+=1
ans=0
for i in range(38):
    ans+=d[i]*s[i]
print(ans)

Fixed submission:
a,b=map(int,input().split())
s=[2**i for i in range(42)]
d=[0]*42
i=1
if ((b+1)//2-a//2)%2==1:
    d[0]+=1
while i<42:
    if s[i]>b:
        break
    elif s[i]>a: 
        a=s[i]
    p,q=a%s[i],a//s[i]
    o,t=b%s[i],b//s[i]
    if q==t:
        if q%2==1:
            if (b-a+1)%2==1:
                d[i]=1
    else:
        h=0
        if q%2==1:
            h+=(q+1)*s[i]-a  
        if t%2==1:
            h+=b-t*s[i]+1
        if h%2==1:
            d[i]=1
    i+=1
ans=0
for i in range(42):
    ans+=d[i]*s[i]
print(ans)
Buggy python submission (verdict: Runtime Error):
import bisect
a,b,q=map(int,input().split())
s=[int(input())for i in range(a)]
t=[int(input())for i in range(b)]
for i in range(q):
    x=int(input())
    c=bisect.bisect_left(s,x)
    d=bisect.bisect_left(t,x)
    p=[]
    if c!=a and d!=b:
        p.append(min(abs(s[c]-x),abs(t[d]-x)))
    if c!=0 and d!=0:
        p.append(min(abs(s[c-1]-x),abs(t[d-1]-x)))
    if c!=a and d!=0:
        p.append(min(abs(s[c]-x)*2+abs(t[d-1]-x),abs(s[c]-x)+2*abs(t[d-1]-x)))
    if c!=0 and d!=b
        p.append(min(abs(s[c-1]-x)*2+abs(t[d]-x),abs(s[c-1]-x)+2*abs(t[d]-x)))
    print(min(p))

Fixed submission:
import bisect
a,b,q=map(int,input().split())
s=[int(input())for i in range(a)]
t=[int(input())for i in range(b)]
for i in range(q):
    x=int(input())
    c=bisect.bisect_left(s,x)
    d=bisect.bisect_left(t,x)
    p=[]
    if c!=a and d!=b:
        p.append(max(abs(s[c]-x),abs(t[d]-x)))
    if c!=0 and d!=0:
        p.append(max(abs(s[c-1]-x),abs(t[d-1]-x)))
    if c!=a and d!=0:
        p.append(min(abs(s[c]-x)*2+abs(t[d-1]-x),abs(s[c]-x)+2*abs(t[d-1]-x)))
    if c!=0 and d!=b:
        p.append(min(abs(s[c-1]-x)*2+abs(t[d]-x),abs(s[c-1]-x)+2*abs(t[d]-x)))
    print(min(p))
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
p=[""]*(n+1)
a=sorted(list(map(int,input().split())))
e=[2,5,5,4,5,6,3,7,6]
d=[]
s=[]
for i in range(len(a)-1,-1,-1):
    if e[a[i]-1] not in s:
        s.append(e[int(a[i])-1])
        d.append(str(a[i]))
        p[e[a[i]-1]]=str(a[i])
for i in range(1,n+1):
    c=[]
    if len(p[i])!=0:
        c.append(int(p[i]))
    for j in range(len(s)):
        if i-s[j]>=0:
            if len(p[i-s[j]])!=0:
                c.append(max(int(p[i-s[j]]+d[j]),int(int(d[j]+p[i-s[j]]))))
    else:
        p[i]=("" if len(c)==0 else str(max(c)))
print(p[-1])

Fixed submission:
n,m=map(int,input().split())
p=[-1]*(n+1)
a=list(map(int,input().split()))
e=[2,5,5,4,5,6,3,7,6]
p[0]=0
for i in range(n+1):
    for j in a:
        if i-e[j-1]>=0:
            p[i]=max(p[i],p[i-e[j-1]]*10+j)
print(p[-1])

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
p=[""]*(n+1)
a=list(map(str,input().split()))
e=[2,5,5,4,5,6,3,7,6]
s=[]
for i in a:
    s.append(e[int(i)-1])
    p[e[int(i)-1]]=str(i)
for i in range(1,n+1):
    c=[]
    if len(p[i])!=0:
        c.append(int(p[i]))
    for j in range(m):
        if i-s[j]>=0:
            if len(p[i-s[j]])!=0:
                c.append(max(int(p[i-s[j]]+a[j]),int(int(a[j]+p[i-s[j]]))))
    else:
        p[i]=("" if len(c)==0 else str(max(c)))
print(p[-1])

Fixed submission:
n,m=map(int,input().split())
p=[-1]*(n+1)
a=list(map(int,input().split()))
e=[2,5,5,4,5,6,3,7,6]
p[0]=0
for i in range(n+1):
    for j in a:
        if i-e[j-1]>=0:
            p[i]=max(p[i],p[i-e[j-1]]*10+j)
print(p[-1])
Buggy python submission (verdict: Runtime Error):
t,x=map(int,inpyt().split())
print(t/x)

Fixed submission:
t,x=map(int,input().split())
print(t/x)
Buggy python submission (verdict: Runtime Error):
import numpy
n,k=map(int,input().split())
a=list(map(int,input().split()))
d=max(a)
def p(x):
    return len(bin(x))-2
e=p(k)
f=p(d)
h=[]
if e>=f:
    for i in range(n):
        l=bin(a[i])
        h.append(list("0"*(e-len(l)+2)+l[2:]))
else:
    for i in range(n):
        l=bin(a[i])
        h.append(list("0"*(f-len(l)+2)+l[2:]))
p=numpy.array(h)
p=p.T
p=p.tolist()
c=0
if k==0:
    print(sum(a))
else:
    ans=0
    for i in range(len(p)):
        o=p[i].count("1")
        if o<n/2 and k>=2**(len(p)-i-1)
            c+=(n-o)*(2**(len(p)-i-1))
            k-=2**(len(p)-i-1)
        else:
            c+=o*(2**(len(p)-i-1))
    print(c)

Fixed submission:
import numpy
n,k=map(int,input().split())
a=list(map(int,input().split()))
d=max(a)
def p(x):
    return len(bin(x))-2
e=p(k)
f=p(d)
h=[]
if e>=f:
    for i in range(n):
        l=bin(a[i])
        h.append(list("0"*(e-len(l)+2)+l[2:]))
else:
    for i in range(n):
        l=bin(a[i])
        h.append(list("0"*(f-len(l)+2)+l[2:]))
p=numpy.array(h)
p=p.T
p=p.tolist()
c=0
if k==0:
    print(sum(a))
else:
    ans=0
    for i in range(len(p)):
        o=p[i].count("1")
        if o<n/2 and k>=2**(len(p)-i-1):
            c+=(n-o)*(2**(len(p)-i-1))
            k-=2**(len(p)-i-1)
        else:
            c+=o*(2**(len(p)-i-1))
    print(c)
Buggy python submission (verdict: Runtime Error):
input()
s=[list(map(int,input().split()))for i in range(n)]
print(sum(sorted([x[1]+x[0] for x in s])[::-2])-sum([x[1]for x in s]))

Fixed submission:
n=int(input())
s=[list(map(int,input().split()))for i in range(n)]
print(sum(sorted([x[1]+x[0] for x in s])[::-2])-sum([x[1]for x in s]))

Buggy python submission (verdict: Runtime Error):
input()
s=[list(map(int,input().split()))for i in range(n)]
print(sum(sorted([x[1]+x[0] for x in s])[::-2])-sum([x[1]for x in s]))

Fixed submission:
n=int(input())
s=[list(map(int,input().split()))for i in range(n)]
print(sum(sorted([x[1]+x[0] for x in s])[::-2])-sum([x[1]for x in s]))

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=[]
t=[]
for i in range(n):
    a,b=map(int,input().split())
    s.append([a,b,i])
    t.append([b,a,i])
s.sort()
t.sort()
r=0
q=0
p=[]
for i in range(n):
    if i%2!=1:
        while s[-1][2] in p:
            s.pop(-1)
        else:
            r+=s[-1][0]
            p.append(s[-1][2])
    else:
        while t[-1][2] in p:
            t.pop(-1)
        else:
            q+=t[-1][0]
            p.append(t[-1][2])
print(r-q)

Fixed submission:
n=int(input())
s=[list(map(int,input().split()))for i in range(n)]
print(sum(sorted([x[1]+x[0] for x in s])[::-2])-sum([x[1]for x in s]))
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
s=[]
d=[]
p=[]
t=[]
for i in range(n):
    a,b=map(int,input().split())
    p.append(b)
    if a not in s:
        s.append(a)
        d.append([b])
    else:
        d[s.index(a)].append(b)    
for i in range(len(s)):
    d[i].sort()
    t.append(d[i][-1])
t.sort()
p.sort()
r=[]
q=0
g=0
for i in range(k):
    if i<=len(t)+1:
        r.append(t[-1])
        q+=t[-1]
        g+=1
        p.pop(p.index(t[-1]))
        t.pop(-1)
    else:
        q+=sum(p[n-k+len(t):])
        del p[n-k+len(t):]
r.sort()
while r[0]+2*g-1<p[-1]:
    q+=p[-1]-r[0]
    g-=1
    p.pop(-1)
    r.pop(0)
print(g**2+q)

Fixed submission:
n,k=map(int,input().split())
a=sorted([list(map(int,input().split()))for i in range(n)],key=lambda x:-x[1])
t=[0]*(n+1)
p,q=0,0
for i in a[:k]:
    p+=i[1]
    if t[i[0]]==0:
        q+=1
    t[i[0]]+=1
s=0
d=p+q*q
c=a[:k][::-1]
for i in a[k:]:
    if t[i[0]]==0:
        while s!=k:
            if t[c[s][0]]==1:
                s+=1
            else:
                break
        if s==k:
            break
        else:
            t[i[0]]+=1
            p-=c[s][1]-i[1]
            q+=1
            d=max(d,p+q*q)
            s+=1
print(d)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
h=list(map(int,input().split()))
s=[float("INF")]*n
s[0]=0
for i in range(n):
    for j in range(k+1):
        if i+j<n:
            s[i+j]=min(s[i]+abs(h[i+j]-h[i]),s[i+j])
        else:
            break
print(s[-1])

Fixed submission:
n,k=map(int,input().split())
s=[0]*n
a=list(map(int,input().split()))
for i,h in enumerate(a):
    if i!=0:
        g=0 if i-k<0 else i-k
        s[i]=min([abs(h-d)+p for d,p in zip(a[g:i],s[g:i])])
print(s[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
h=list(map(int,input().split()))
s=[float("INF")]*n
s[0]=0
for i in range(n):
    for j in range(k+1):
        if i+j<n:
            s[i+j]=min(s[i]+abs(h[i+j]-h[i]),s[i+j])
        else:
            break
print(s[-1])

Fixed submission:
n,k=map(int,input().split())
s=[0]*n
a=list(map(int,input().split()))
for i,h in enumerate(a):
    if i!=0:
        g=0 if i-k<0 else i-k
        s[i]=min([abs(h-d)+p for d,p in zip(a[g:i],s[g:i])])
print(s[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
s=[0]*n
a=list(map(int,input().split()))
for i in range(1,n):
    c=float("inf")
    for j in range(i-1,max(-1,i-1-k),-1):
        c=min(c,abs(a[i]-a[j])+s[j])
    else:
        s[i]=c
print(s[-1])

Fixed submission:
n,k=map(int,input().split())
s=[0]*n
a=list(map(int,input().split()))
for i,h in enumerate(a):
    if i!=0:
        g=0 if i-k<0 else i-k
        s[i]=min([abs(h-d)+p for d,p in zip(a[g:i],s[g:i])])
print(s[-1])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict as d
s=d(int)
s[0]=0
n,w=map(int,input().split())
for i in range(n):
    q,v=map(int,input().split())
    c=s.copy()
    for p,r in c.items():
        if p+q<=w:
            s[p+q]=max(s[p+q],r+v)
print(max(s.values()))


Fixed submission:
import numpy as np
n,a=map(int,input().split())
s=np.full(n*1000+1,a+1)
s[0]=0
for i in range(n):
    w,v=map(int,input().split())
    s[v:]=np.minimum(s[v:],s[:-v]+w)
print(np.max(np.where(s<=a)))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict as d
s=d(int)
s[0]=0
n,w=map(int,input().split())
for i in range(n):
    q,v=map(int,input().split())
    c=s.copy()
    for p,r in c.items():
        if p+q<=w:
            s[p+q]=max(s[p+q],r+v)
print(max(s.values()))

Fixed submission:
import numpy as np
n,a=map(int,input().split())
s=np.full(n*1000+1,a+1)
s[0]=0
for i in range(n):
    w,v=map(int,input().split())
    s[v:]=np.minimum(s[v:],s[:-v]+w)
print(np.max(np.where(s<=a)))

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict as f
n,s=map(int,input().split())
k=f(int)
k[0]=0
g=0
for i in range(n):
    w,v=map(int,input().split())
    c=list(k)
    for i in range(len(c)-1,-1,-1):
        if c[k[i]+v]!=0:
            c[k[i]+v]=min(c[k[i]]+w,c[k[i]+v])
        else:
            c[k[i]+v]=c[k[i]]+w
        if c[k[i]+v]<=s:
            g=max(g,k[i]+v)
print(g)              

Fixed submission:
import numpy as np
n,a=map(int,input().split())
s=np.full(n*1000+1,a+1)
s[0]=0
for i in range(n):
    w,v=map(int,input().split())
    s[v:]=np.minimum(s[v:],s[:-v]+w)
print(np.max(np.where(s<=a)))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
n,s=map(int,input().split())
k=defaultdict(int)
k[0]=0
d=0
for i in range(n):
    w,v=map(int,input().split())
    c=list(k)
    for i in range(len(c)-1,-1,-1):
        if c[i]+w<=s:
            if k[c[i]+w]!=0:
                k[c[i]+w]=max(k[c[i]+w],k[c[i]]+v)
            else:
                k[c[i]+w]=k[c[i]]+v
            d=max(d,k[c[i]+w])
print(d)              

Fixed submission:
import numpy as np
n,a=map(int,input().split())
s=np.full(n*1000+1,a+1)
s[0]=0
for i in range(n):
    w,v=map(int,input().split())
    s[v:]=np.minimum(s[v:],s[:-v]+w)
print(np.max(np.where(s<=a)))

Buggy python submission (verdict: Runtime Error):
import numpy as np
n,w=map(int,input().split())
a=np.zeros([n,w+1],dtype=int)
c,d=map(int,input().split())
a[0][c:]=d
for i in range(1,n):
    e,f=map(int,input().split())
    a[i][:e]=a[i-1][:e]
    a[i][e:]=np.maximum(a[i-1][e:],a[i-1][:-e]+f)
print(a[-1][-1])

Fixed submission:
import numpy as np
n,a=map(int,input().split())
s=np.full(n*1000+1,a+1)
s[0]=0
for i in range(n):
    w,v=map(int,input().split())
    s[v:]=np.minimum(s[v:],s[:-v]+w)
print(np.max(np.where(s<=a)))