Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
K, S = map(int, input().split())
counter = 0
for x in range(K+1):
  if x > S:
    break
  for y in range(K+1):
    if x+y > S:
      break
    for z in range(K+1):
      if x+y+z == S:
        counter += 1
      if x+y+z > S:
        break
print(counter)

Fixed submission:
K, S = map(int, input().split())
counter = 0
for x in range(K+1):
  for y in range(K+1):
    z = S - x - y
    if z >= 0 and z <= K:
      counter += 1
print(counter)

Buggy python submission (verdict: Time Limit Exceeded):
K, S = map(int, input().split())
counter = 0
for x in range(K+1):
  for y in range(K+1):
    for z in range(K+1):
      if x+y+z == S:
        counter += 1
print(counter)

Fixed submission:
K, S = map(int, input().split())
counter = 0
for x in range(K+1):
  for y in range(K+1):
    z = S - x - y
    if z >= 0 and z <= K:
      counter += 1
print(counter)
Buggy python submission (verdict: Runtime Error):
a,b,c = linst(map(int,input()))
if a*b < c:
  print(a*b)
else:
  print(c)


Fixed submission:
n,a,b = map(int,input().split())
if a*n < b:
  print(a*n)
else:
  print(b)
Buggy python submission (verdict: Runtime Error):
s = input()
ans = 'No'
a = {x for x in s}
if len(a) == 2:
  if a.count(a[0]) == 2 and a.count(a[1]) == 2:
    ans = 'Yes'
    
print(ans)

Fixed submission:
s = input()
ans = 'No'
a = list({x for x in s})
if len(a) == 2:

  if s.count(a[0]) == 2 and s.count(a[1]) == 2:
    ans = 'Yes'
    
print(ans)
Buggy python submission (verdict: Runtime Error):
H, W = list(map(int, input().split()))
h, w = list(map(int, input().split()))

white = H*W
if h 
black = h*W + w*(H-h)

print(white-black)

Fixed submission:
H, W = list(map(int, input().split()))
h, w = list(map(int, input().split()))

white = H*W
black = h*W + w*(H-h)

print(white-black)
Buggy python submission (verdict: Runtime Error):
N, M, C = list(map(int, input().split()))
B = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N)]
cnt = 0
for x in A:
  total = sum([A[i]*B[i] for i in range(M)])
  total += C
  if total > 0:
    cnt+= 1
    
print(cnt)

Fixed submission:
N, M, C = list(map(int, input().split()))
B = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N)]
cnt = 0
for x in A:
  total = sum([x[i]*B[i] for i in range(M)])
  total += C
  if total > 0:
    cnt+= 1
    
print(cnt)
Buggy python submission (verdict: Runtime Error):
import math


n = int(input())
t,a = list(map(int,input().split()))
h = list(map(int, input().split()))
ans = math.inf
okok = 0
for i in range(0,n):
  if(ans > abs(a-t-h[i]*0.006)):
    ans = abs(a-t-h[i]*0.006)
    okok = i+1

print(okok)

Fixed submission:
n = int(input())
t,a = list(map(int,input().split()))
h = list(map(int, input().split()))
ans = 1000000000
okok = 0

for i in range(0,n):
  if(ans > abs(a-(t-h[i]*0.006))):
    ans = abs(a-(t-h[i]*0.006))
    okok = i+1

print(okok)

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


n = int(input())
t,a = list(map(int,input().split()))
h = list(map(int, input().split()))
ans = math.inf
okok = 0
for i in range(0,n):
  if(ans > abs(a-t-h[i]*0.006)):
    ans = abs(a-t-h[i]*0.006)
    okok = i+1

print(okok)

Fixed submission:
n = int(input())
t,a = list(map(int,input().split()))
h = list(map(int, input().split()))
ans = 1000000000
okok = 0

for i in range(0,n):
  if(ans > abs(a-(t-h[i]*0.006))):
    ans = abs(a-(t-h[i]*0.006))
    okok = i+1

print(okok)
Buggy python submission (verdict: Runtime Error):
n, t = list(map(int,input().split()))
list1 = []
list2 = []
for i in range(0,int(n)):
  list1.append(list(map(int, input().split())))

for i in list1:
  if int(i[1]) <= int(t):
    list2.append(i)

list2.sort()
print(list2[0][0])

Fixed submission:
n, t = list(map(int,input().split()))
list1 = []
list2 = []
for i in range(0,n):
  list1.append(list(map(int, input().split())))

for i in list1:
  if int(i[1]) <= t:
    list2.append(i)

if(list2):
  list2.sort()
  print(list2[0][0])
else:
  print("TLE")
Buggy python submission (verdict: Time Limit Exceeded):
l,r = [int(u) for u in input().split(" ")]

a = []
for i in range(l,r+1):
  p = [((i%2019)*j)%2019 for j in set([u%2019 for u in range(i+1,r+1)])]
  if len(p)>0:
    a.append(min(p))
print(min(a))

Fixed submission:
import math

l,r = [int(u) for u in input().split(" ")]

if math.floor(l/2019)<math.floor(r/2019):
  print(0)
else:
  a = []
  for i in range(l,r+1):
    p = [((i%2019)*j)%2019 for j in set([u%2019 for u in range(i+1,r+1)])]
    if len(p)>0:
      a.append(min(p))
  print(min(a))
Buggy python submission (verdict: Runtime Error):
import math
r,g,b,n = [int(u) for u in input().split(" ")]
i = 0
for ir in range(math.floor(n/r)+1):
  if ir*r>n:
    break
  for ig in range(math.floor(n/g)+1):
    if ig*g>n:
      break
    y = n- (ir*r+ig*g)
    if y<0:
      break
    if y>=0 and y%b==0:
      #print(ir,ig,y/b)
      i+=1
print(i)

Fixed submission:
n,k = [int(u) for u in input().split(" ")]
print(n-k+1)
Buggy python submission (verdict: Time Limit Exceeded):
import math
r,g,b,n = [int(u) for u in input().split(" ")]
i = 0
for ir in range(math.floor(n/r)+1):
  if ir*r>n:
    break
  for ig in range(math.floor(n/g)+1):
    y = n - (ir*r+ig*g)
    if y<0:
      break
    if y>=0 and y%b==0:
      #print(ir,ig,y/b)
      i+=1
      continue
print(i)

Fixed submission:
import math
r,g,b,n = [int(u) for u in input().split(" ")]
i = 0
for ir in range(math.floor(n/r)+1):
  if ir*r==n:
    i+=1
    break
  elif ir*r>n:
    break
  for ig in range(math.floor(n/g)+1):
    y = n - (ir*r+ig*g)
    if y<0:
      break
    if y%b==0:
      #print(ir,ig,y/b)
      i+=1
      continue
print(i)

Buggy python submission (verdict: Time Limit Exceeded):
import math
r,g,b,n = [int(u) for u in input().split(" ")]
i = 0
for ir in range(math.floor(n/r)+1):
  if ir*r>n:
    break
  for ig in range(math.floor(n/g)+1):
    if ig*g>n:
      break
    y = n- (ir*r+ig*g)
    if y<0:
      break
    if y>=0 and y%b==0:
      #print(ir,ig,y/b)
      i+=1
print(i)

Fixed submission:
import math
r,g,b,n = [int(u) for u in input().split(" ")]
i = 0
for ir in range(math.floor(n/r)+1):
  if ir*r==n:
    i+=1
    break
  elif ir*r>n:
    break
  for ig in range(math.floor(n/g)+1):
    y = n - (ir*r+ig*g)
    if y<0:
      break
    if y%b==0:
      #print(ir,ig,y/b)
      i+=1
      continue
print(i)

Buggy python submission (verdict: Time Limit Exceeded):
import math
r,g,b,n = [int(u) for u in input().split(" ")]
i = 0
for ir in range(math.floor(n/r)+1):
  if ir*r>n:
    break
  for ig in range(math.floor(n/g)+1):
    if ig*g>n:
      break
    y = n- (ir*r+ig*g)
    if y>=0 and y%b==0:
      #print(ir,ig,y/b)
      i+=1
print(i)

Fixed submission:
import math
r,g,b,n = [int(u) for u in input().split(" ")]
i = 0
for ir in range(math.floor(n/r)+1):
  if ir*r==n:
    i+=1
    break
  elif ir*r>n:
    break
  for ig in range(math.floor(n/g)+1):
    y = n - (ir*r+ig*g)
    if y<0:
      break
    if y%b==0:
      #print(ir,ig,y/b)
      i+=1
      continue
print(i)
Buggy python submission (verdict: Runtime Error):
h,w,a,b=map(int,input().split())
if h==1:
    print('0'*a+'1'*(w-a))
elif w==1:
    for _ in [0]*b:
        print(0)
    for _ in [0]*(h-b):
        print(1)
elif h%b!=0 or w%a!=0 or h//b!=w//a:
    print('No')
else:
    ans=[[0]*w for _ in [0]*h]
    for i in range(h):
        for j in range(a*(i//b),a*(i//b)+a):
            ans[i][j]=1
    for x in ans:
        print(*x,sep='')

Fixed submission:
h,w,a,b=map(int,input().split())
for _ in [0]*b:
    print('0'*a+'1'*(w-a))
for _ in [0]*(h-b):
    print('1'*a+'0'*(w-a))

Buggy python submission (verdict: Runtime Error):
h,w,a,b=map(int,input().split())
if h==1:
    print('0'*a+'1'*(w-a))
elif w==1:
    for _ in [0]*a:
        print(0)
    for _ in [0]*(n-a):
        print(1)
elif h%a!=0 or w%b!=0 or h//a!=w//b:
    print('No')
else:
    ans=[[0]*w for _ in [0]*h]
    for i in range(h):
        for j in range(b*(i//a),b*(i//a)+b):
            ans[i][j]=1
    for x in ans:
        print(*x,sep='')

Fixed submission:
h,w,a,b=map(int,input().split())
for _ in [0]*b:
    print('0'*a+'1'*(w-a))
for _ in [0]*(h-b):
    print('1'*a+'0'*(w-a))
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
l=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:[x[0],-x[1]])+[[float('inf'),0]]
for i in range(n):l[i][0]-=1
w=[n]*m
for i in range(m):
    j=0
    while l[j][0]<=i:
        if l[j][1]>l[w[i]][1] and j not in w:
            w[i]=j
        j+=1
print(sum(l[w[i]][1] for i in range(m)))

Fixed submission:
from heapq import heappop, heappush

n,m=map(int,input().split())
a=[]
for i in range(n):
    heappush(a,list(map(int,input().split())))
heap=[]
s=0
for i in range(m):
    while 1:
        if len(a)==0:break
        else:
            if a[0][0]==i+1:heappush(heap,-heappop(a)[1])
            else:break
    if len(heap)>0:s+=-heappop(heap)
print(s)

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
l=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:[x[0],-x[1]])+[[float('inf'),float('inf')]]
for i in range(n):l[i][0]-=1
w=[0]*m
for i in range(m):
    j=0
    k=-1
    while l[j][0]<=i:
        if l[j][1]>w[i]:
            w[i]=l[j][1]
            k=j
        j+=1
    if k>=0:del l[k]
print(sum(w))

Fixed submission:
from heapq import heappop, heappush

n,m=map(int,input().split())
a=[]
for i in range(n):
    heappush(a,list(map(int,input().split())))
heap=[]
s=0
for i in range(m):
    while 1:
        if len(a)==0:break
        else:
            if a[0][0]==i+1:heappush(heap,-heappop(a)[1])
            else:break
    if len(heap)>0:s+=-heappop(heap)
print(s)

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
l=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:[x[0],-x[1]])+[[-1,-1]]
for i in range(n):l[i][0]-=1
w=[0]*(m+1)
i=0
while i<n:
    j=l[i][0]
    s=j
    while l[i][0]==j:
        while w[s]>=l[i][1]:s+=1
        if s<m:w[s]=l[i][1]
        i+=1
print(sum(w))


Fixed submission:
from heapq import heappop, heappush

n,m=map(int,input().split())
a=[]
for i in range(n):
    heappush(a,list(map(int,input().split())))
heap=[]
s=0
for i in range(m):
    while 1:
        if len(a)==0:break
        else:
            if a[0][0]==i+1:heappush(heap,-heappop(a)[1])
            else:break
    if len(heap)>0:s+=-heappop(heap)
print(s)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
def sol():
    n=int(input())
    new=[int(input()) for _ in [0]*n]
    a=[new[0]]
    for i in range(1,n):
        if a[-1]>=new[i]:a.append(new[i])
        else:
            for j in range(len(a)):
                if a[j]<new[i]:a[j]=new[i];break
    print(len(a))
sol()

Fixed submission:
print(3*int(input())**2)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[int(input()) for _ in [0]*n]
for i in range(n):
    print(max(a[:i]+a[i+1:]))

Fixed submission:
n=int(input())
a=[int(input()) for _ in [0]*n]
M=max(a)
k=a.index(M)
m=max(a[:k]+a[k+1:])
for i in range(n):
    if i!=k:print(M)
    else:print(m)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
n=len(s)
for i in range(10,-1,-1):
    t='1'*2**i+'0'*2**i
    while t in s:
        s=s.replace(t,'')
for i in range(10,-1,-1):
    t='0'*2**i+'1'*2**i
    while t in s:
        s=s.replace(t,'')
print(n-len(s))


Fixed submission:
s=input()
print(len(s)-abs(s.count('1')-s.count('0')))

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
n=len(s)
while '10' in s:
    s=s.replace('10','')
while '01' in s:
    s=s.replace('01','')
print(n-len(s))

Fixed submission:
s=input()
print(len(s)-abs(s.count('1')-s.count('0')))
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
h=list(map(int,input().split()))
d=[float('inf')]*n
d[0]=0
for i in range(n-1):
    for j in range(1,min(k+1,n-i)):
        d[i+j]=min(d[i+j],d[i]+abs(h[i+j]-h[i]))
print(d[-1])

Fixed submission:
n=int(input())
h=list(map(int,input().split()))
d=[0]*n
d[1]=abs(h[1]-h[0])
for i in range(2,n):
    d[i]=min(d[i-1]+abs(h[i]-h[i-1]),d[i-2]+abs(h[i]-h[i-2]))
print(d[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
def sol():
    n,k=map(int,input().split())
    h=list(map(int,input().split()))
    d=[float('inf')]*n
    d[0]=0
    for i in range(1,n):
        d[i]=min(d[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i))
    print(d[n-1])
sol()

Fixed submission:
n,k=map(int,input().split())
h=list(map(int,input().split()))
d=[float('inf')]*n
d[0]=0
for i in range(n-1):
    for j in range(1,min(k+1,n-i)):
        d[i+j]=min(d[i+j],d[i]+abs(h[i+j]-h[i]))
print(d[-1])

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

Fixed submission:
n,k=map(int,input().split())
h=list(map(int,input().split()))
d=[float('inf')]*n
d[0]=0
for i in range(n-1):
    for j in range(1,min(k+1,n-i)):
        d[i+j]=min(d[i+j],d[i]+abs(h[i+j]-h[i]))
print(d[-1])

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

Fixed submission:
n,k=map(int,input().split())
h=list(map(int,input().split()))
d=[float('inf')]*n
d[0]=0
for i in range(n-1):
    for j in range(1,min(k+1,n-i)):
        d[i+j]=min(d[i+j],d[i]+abs(h[i+j]-h[i]))
print(d[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
dp=[0 for _ in range(w+1)]
for i in range(n):
    for j in range(w,l[i][0]-1,-1):
        dp[j]=max(dp[j],dp[j-l[i][0]]+l[i][1])
print(max(dp))

Fixed submission:
n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
dp=[0 for _ in range(w+1)]
for i in range(n):
    for j in range(w,l[i][0]-1,-1):
        dp[j]=max(dp[j],dp[j-l[i][0]]+l[i][1])
print(max(dp))

Buggy python submission (verdict: Time Limit Exceeded):
n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
dp=[[0 for _ in range(w+1)] for _ in range(n)]
dp[0][l[0][0]]=l[0][1]
for i in range(1,n):
    for j in range(w+1):
        if j-l[i][0]>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-l[i][0]]+l[i][1])
        else:dp[i][j]=dp[i-1][j]
print(max(dp[n-1]))

Fixed submission:
n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
dp=[0 for _ in range(w+1)]
for i in range(n):
    for j in range(w,l[i][0]-1,-1):
        dp[j]=max(dp[j],dp[j-l[i][0]]+l[i][1])
print(max(dp))
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=input()
print(max(len(set(s[:i])&set(s[i:])) for i in range(1,n-1)))

Fixed submission:
n=int(input())
s=input()
print(max(len(set(s[:i])&set(s[i:])) for i in range(1,n)))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
c=0
L=[[0,0],[a[0],a[0]]]
for i in range(1,n):
    L.append([L[-1][0]^a[i],L[-1][1]+a[i]])
for l in range(1,n):
    for r in range(l+1,n+1):
        if L[l-1][0]^L[r][0]==L[r][1]-L[l-1][1]:
            c+=1
print(c+n)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
j=0
c=0
s=a[0]
for i in range(n):
    if j<i:
        j=i
        s=a[i]
    if j<n-1:
        while s&a[j+1]==0:
            s|=a[j+1]
            j+=1
            if j==n-1:
                break
    c+=j-i+1
    s^=a[i]
print(c)
Buggy python submission (verdict: Runtime Error):
s=input()
print(sorted(list(set([s[i:j] for i in range(len(s)) for j in range(i+1,len(s)+1)])))[int(input())-1])

Fixed submission:
s=input()
n=len(s)
k=int(input())
l=[]
for i in range(1,6):
    if n>=i:l=l+[s[j:j+i] for j in range(n-i+1)]
print(sorted(list(set(l)))[k-1])
Buggy python submission (verdict: Time Limit Exceeded):
a,b,k=map(int,input().split())
print(*sorted((set(range(a,a+k))|set(range(b-k+1,b+1)))&set(range(a,b+1))),sep='\n')

Fixed submission:
a,b,k=map(int,input().split())
print(*sorted(set(range(a,min(b+1,a+k)))|set(range(max(b-k+1,a),b+1))),sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
B=[0]*n
j=0
for i in range(n):
    while b[i]>=c[j] and j<n-1:j+=1
    B[i]=n-j
ans=0
j=0
for i in range(n):
    while a[i]>=b[j] and j<n-1:j+=1
    if a[i]<b[j]:ans+=sum(B[j:])
print(ans)

Fixed submission:
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
B=[0]*n
j=0
for i in range(n):
    while b[i]>=c[j] and j<n-1:j+=1
    if b[i]<c[j]:B[i]=n-j
ans=0
s=sum(B)
j=0
for i in range(n):
    while a[i]>=b[j] and j<n-1:s-=B[j];j+=1
    if a[i]<b[j]:ans+=s
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
x=[0]*n
y=[0]*n
for i in range(n):
    x[i],y[i]=map(int,input().split())
ans=float('inf')
for i1 in range(n):
    for i2 in range(i1+1,n):
        for j1 in range(n):
            for j2 in range(j1+1,n):
                a,b=sorted([x[i1],x[i2]])
                c,d=sorted([y[j1],y[j2]])
                cnt=0
                for i in range(n):
                    if a<=x[i]<=b and c<=y[i]<=d:
                        cnt+=1
                if cnt>=k:
                    ans=min(ans,(b-a)*(d-c))
print(ans)

Fixed submission:
n,k=map(int,input().split())
x=[0]*n
y=[0]*n
for i in range(n):
    x[i],y[i]=map(int,input().split())
ans=float('inf')
for i1 in range(n):
    for i2 in range(i1+1,n):
        for j1 in range(n):
            for j2 in range(j1+1,n):
                a,b=sorted([x[i1],x[i2]])
                c,d=sorted([y[j1],y[j2]])
                cnt=0
                for i in range(n):
                    if a<=x[i]<=b and c<=y[i]<=d:
                        cnt+=1
                if cnt>=k:
                    ans=min(ans,(b-a)*(d-c))
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
n=int(input())
t=[int(input()) for _ in [0]*n]

d=t[0]
for i in range(1,n):
    d=(t[i]*d)//math.gcd(t[i],d)
print(d)

Fixed submission:
import fractions
n=int(input())
t=[int(input()) for _ in [0]*n]

d=t[0]
for i in range(1,n):
    d=(t[i]*d)//fractions.gcd(t[i],d)
print(d)

Buggy python submission (verdict: Runtime Error):
import math
n=int(input())
t=[int(input()) for _ in [0]*n]

d=t[0]
print(d)
for i in range(1,n):
    d=(t[i]*d)//math.gcd(t[i],d)
    print(d)

Fixed submission:
import fractions
n=int(input())
t=[int(input()) for _ in [0]*n]

d=t[0]
for i in range(1,n):
    d=(t[i]*d)//fractions.gcd(t[i],d)
print(d)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n,m=map(int,input().split())
L=[list(map(int,input().split())) for _ in [0]*m]
for l in L:
    if l[0]==1:
        if [l[1],n] in L:print('POSSIBLE');break
else:print('IMPOSSIBLE')

Fixed submission:
import sys
input = sys.stdin.readline

n,m=map(int,input().split())
a=[]
b=[]
for _ in [0]*m:
    l=list(map(int,input().split()))
    if l[0]==1:a.append(l[1])
    if l[1]==n:b.append(l[0])
print('POSSIBLE' if set(a)&set(b) else 'IMPOSSIBLE')

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*m]
for i in range(2,n):
    if [1,i] in l and [i,n] in l:print('POSSIBLE');break
else:print('IMPOSSIBLE')

Fixed submission:
import sys
input = sys.stdin.readline

n,m=map(int,input().split())
a=[]
b=[]
for _ in [0]*m:
    l=list(map(int,input().split()))
    if l[0]==1:a.append(l[1])
    if l[1]==n:b.append(l[0])
print('POSSIBLE' if set(a)&set(b) else 'IMPOSSIBLE')

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*m]
if all([1,i] not in l or [i,n] not in l for i in range(2,n)):print('IM',end='')
print('POSSIBLE')

Fixed submission:
import sys
input = sys.stdin.readline

n,m=map(int,input().split())
a=[]
b=[]
for _ in [0]*m:
    l=list(map(int,input().split()))
    if l[0]==1:a.append(l[1])
    if l[1]==n:b.append(l[0])
print('POSSIBLE' if set(a)&set(b) else 'IMPOSSIBLE')
Buggy python submission (verdict: Time Limit Exceeded):
n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
dp=[0 for _ in range(w+1)]
for i in range(n):
    for j in range(w,l[i][0]-1,-1):
        dp[j]=max(dp[j],dp[j-l[i][0]]+l[i][1])
print(dp[-1])

Fixed submission:
n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
l1,l2,l3,l4=[],[],[],[]
a=l[0][0]
for i in range(n):
    if l[i][0]==a:
        l1.append(l[i][1])
    elif l[i][0]==a+1:
        l2.append(l[i][1])
    elif l[i][0]==a+2:
        l3.append(l[i][1])
    else:
        l4.append(l[i][1])
l1.sort(reverse=True)
l2.sort(reverse=True)
l3.sort(reverse=True)
l4.sort(reverse=True)
ans=0
for h in range(len(l1)+1):
    for i in range(len(l2)+1):
        for j in range(len(l3)+1):
            for k in range(len(l4)+1):
                if a*h+(a+1)*i+(a+2)*j+(a+3)*k<=w:
                    ans=max(ans,sum(l1[:h])+sum(l2[:i])+sum(l3[:j])+sum(l4[:k]))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
dp=[0 for _ in range(w+1)]
for i in range(n):
    for j in range(w,l[i][0]-1,-1):
        dp[j]=max(dp[j],dp[j-l[i][0]]+l[i][1])
print(dp[-1])

Fixed submission:
n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
l1,l2,l3,l4=[],[],[],[]
a=l[0][0]
for i in range(n):
    if l[i][0]==a:
        l1.append(l[i][1])
    elif l[i][0]==a+1:
        l2.append(l[i][1])
    elif l[i][0]==a+2:
        l3.append(l[i][1])
    else:
        l4.append(l[i][1])
l1.sort(reverse=True)
l2.sort(reverse=True)
l3.sort(reverse=True)
l4.sort(reverse=True)
ans=0
for h in range(len(l1)+1):
    for i in range(len(l2)+1):
        for j in range(len(l3)+1):
            for k in range(len(l4)+1):
                if a*h+(a+1)*i+(a+2)*j+(a+3)*k<=w:
                    ans=max(ans,sum(l1[:h])+sum(l2[:i])+sum(l3[:j])+sum(l4[:k]))
print(ans)

Buggy python submission (verdict: Runtime Error):
n,W=map(int,input().split())
dp=[0]*(W+1)
for _ in [0]*n:
    w,v=map(int,input().split())
    for i in range(W,w-1,-1):
        dp[i]=max(dp[i],dp[i-w]+v)
print(dp[-1])

Fixed submission:
n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
l1,l2,l3,l4=[],[],[],[]
a=l[0][0]
for i in range(n):
    if l[i][0]==a:
        l1.append(l[i][1])
    elif l[i][0]==a+1:
        l2.append(l[i][1])
    elif l[i][0]==a+2:
        l3.append(l[i][1])
    else:
        l4.append(l[i][1])
l1.sort(reverse=True)
l2.sort(reverse=True)
l3.sort(reverse=True)
l4.sort(reverse=True)
ans=0
for h in range(len(l1)+1):
    for i in range(len(l2)+1):
        for j in range(len(l3)+1):
            for k in range(len(l4)+1):
                if a*h+(a+1)*i+(a+2)*j+(a+3)*k<=w:
                    ans=max(ans,sum(l1[:h])+sum(l2[:i])+sum(l3[:j])+sum(l4[:k]))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))

b=a[:]
for i in range(n):
    if i%2:b[i]=min(-sum(b[j] for j in range(i))-1,b[i])
    else: b[i]=max(-sum(b[j] for j in range(i))+1,b[i])
s=sum(abs(b[i]-a[i]) for i in range(n))

c=a[:]
for i in range(n):
    if i%2:c[i]=max(-sum(c[j] for j in range(i))+1,c[i])
    else: c[i]=min(-sum(c[j] for j in range(i))-1,c[i])
t=sum(abs(c[i]-a[i]) for i in range(n))

print(min(s,t))

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

s1=c1=s2=c2=0
for i in range(n):
    if i%2:
        c1+=max(0,a[i]+s1+1); s1+=min(-s1-1,a[i])
        c2+=max(0,-s2+1-a[i]); s2+=max(-s2+1,a[i])
    else:
        c1+=max(0,-s1+1-a[i]); s1+=max(-s1+1,a[i])
        c2+=max(0,a[i]+s2+1); s2+=min(-s2-1,a[i])
print(min(c1,c2))