Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def gcd(a,b):
        while b!=0:
                a,b=b,a%b
        return a

A, B, C, D = map(int, input().split(" "))
ans = 0
Bc = B // C
Bd = B // D
ck = 0

asb = C*D//ck
Bs = B//asb

newb = B - Bc - Bd + Bs

Ac = (A-1) // C
Ad = (A-1) // D
As = (A-1)//asb

newa = (A-1)-Ac-Ad+As

print(int(newb-newa))

Fixed submission:
def gcd(a,b):
        while b!=0:
                a,b=b,a%b
        return a

A, B, C, D = map(int, input().split(" "))
ans = 0
Bc = B // C
Bd = B // D
ck = gcd(C,D)
asb = C*D//ck
Bs = B//asb

newb = B - Bc - Bd + Bs

Ac = (A-1) // C
Ad = (A-1) // D
As = (A-1)//asb

newa = (A-1)-Ac-Ad+As

print(int(newb-newa))

Buggy python submission (verdict: Runtime Error):
import math
A, B, C, D = map(int, input().split(" "))
ans = 0
Bc = B // C
Bd = B // D

ck = math.gcd(C, D)
asb = C*D/ck
Bs = B//asb

newb = B - Bc - Bd + Bs

Ac = (A-1) // C
Ad = (A-1) // D
As = (A-1)//asb

newa = (A-1)-Ac-Ad+As

print(newb-newa)

Fixed submission:
def gcd(a,b):
        while b!=0:
                a,b=b,a%b
        return a

A, B, C, D = map(int, input().split(" "))
ans = 0
Bc = B // C
Bd = B // D
ck = gcd(C,D)
asb = C*D//ck
Bs = B//asb

newb = B - Bc - Bd + Bs

Ac = (A-1) // C
Ad = (A-1) // D
As = (A-1)//asb

newa = (A-1)-Ac-Ad+As

print(int(newb-newa))
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split(" "))
botlist = []
ans = 0
for n in range(M):
    bot = list(map(int, input().split(" ")))
    
    botlist.append(bot)
#botlist
plist = list(map(int, input().split(" ")))

pushlist = [[]for i in range(2**N)]

for p in range(N):
    M = (2**N)/(p+1)
    for q in range(M):
        for r in range(p+1):
            if q%2 == 0:
                pushlist[r*q] = 0
            else:
                pushlist[r*q] = 1

for A in pushlist:
    g = 0
    for B in botlist:
        cou = 0
        for c in range(B[0]):
            cou += A[B[c]]
        if cou % 2 == plist[g]:
            ans += 1
    g +=1

print(ans)


    





Fixed submission:
N, M = map(int, input().split(" "))
botlist = []
ans = 0
for n in range(M):
    bot = list(map(int, input().split(" ")))
    
    botlist.append(bot)
#botlist
plist = list(map(int, input().split(" ")))

pushlist = [[]for i in range(2**N)]

for p in range(N):
    for q in range(2**N):
        if q % (2**(p+1)) <2**p:
            pushlist[q].append(0)
        else:
            pushlist[q].append(1) 

for A in pushlist:
    #print(A)
    g = 0
    faa = 0
    for B in botlist:
        g += 1
        cou = 0
        for c in range(B[0]):
            cou += A[B[c+1]-1]

        if cou % 2 == plist[g-1]:
            faa += 1
    if faa == M:
        ans += 1
    

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M  = map(int, input().split(" "))
Alist = list(map(int, input().split(" ")))
leng = len(Alist)
ans = 0
#print(Alist)
for i in range(M):
    b, c = map(int, input().split(" "))
    for j in range(b):
        Alist.append(c)

Alist.sort()

for k in range(leng):
    ans += Alist[-k-1]

print(ans)

Fixed submission:
N, M  = map(int, input().split(" "))
Alist = list(map(int, input().split(" ")))
bclist = []
leng = len(Alist)
ans = 0
#print(Alist)
for i in range(M):
    b, c = (map(int, input().split(" ")))
    bclist.append([c,b])
bclist.sort(reverse = True)
#print(bclist)

count = 0
for j in range(M):
    for n in range(bclist[j][1]):
        Alist.append(bclist[j][0])
    count += bclist[j][1]
    if count >= leng:
        break
    

Alist.sort()

for k in range(leng):
    ans += Alist[-k-1]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M  = map(int, input().split(" "))
Alist = list(map(int, input().split(" ")))
Alist.sort()
ans = 0
#print(Alist)
for i in range(M):
    b, c = map(int, input().split(" "))
    for j in range(b):
        if Alist[j] < c:
            Alist[j] = c
        else:
            break
    Alist.sort()

for k in range(N):
    ans += Alist[k]

print(ans)

Fixed submission:
N, M  = map(int, input().split(" "))
Alist = list(map(int, input().split(" ")))
bclist = []
leng = len(Alist)
ans = 0
#print(Alist)
for i in range(M):
    b, c = (map(int, input().split(" ")))
    bclist.append([c,b])
bclist.sort(reverse = True)
#print(bclist)

count = 0
for j in range(M):
    for n in range(bclist[j][1]):
        Alist.append(bclist[j][0])
    count += bclist[j][1]
    if count >= leng:
        break
    

Alist.sort()

for k in range(leng):
    ans += Alist[-k-1]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M  = map(int, input().split(" "))
Alist = list(map(int, input().split(" ")))
Alist.sort()
ans = 0
#print(Alist)
for i in range(M):
    b, c = map(int, input().split(" "))
    for j in range(b):
        if Alist[j] < c:
            Alist[j] = c
    Alist.sort()

for k in range(N):
    ans += Alist[k]

print(ans)

Fixed submission:
N, M  = map(int, input().split(" "))
Alist = list(map(int, input().split(" ")))
bclist = []
leng = len(Alist)
ans = 0
#print(Alist)
for i in range(M):
    b, c = (map(int, input().split(" ")))
    bclist.append([c,b])
bclist.sort(reverse = True)
#print(bclist)

count = 0
for j in range(M):
    for n in range(bclist[j][1]):
        Alist.append(bclist[j][0])
    count += bclist[j][1]
    if count >= leng:
        break
    

Alist.sort()

for k in range(leng):
    ans += Alist[-k-1]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split(" "))
S = input()
for i in range(Q):
    l, r = map(int, input().split(" "))
    ans = 0
    #x = []
    for j in range(l-1, r-1):
        #jにl-1からr-2までを代入する
        #x.append(S[j])
        if S[j]=="A":
            if S[j+1]=="C":
                ans += 1
            #else:
                #ans += 0
        #else:
            #ans += 0
    print(ans)
    #print(x)


Fixed submission:
N, Q = map(int, input().split(" "))
S = input()
t = [0]*(N+1)
#N+1個の0を持つリスト
for i in range(N):
    if S[i:i+2] == "AC":
        #S[x, y]は文字列Sのx番目からy-1番目までの文字列
        t[i + 1] = t[i] + 1
    else:
        t[i + 1] = t[i]
#S=0123...
#T=0123...

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1]-t[l-1])
#l, r = 123...
#r番目までのときのACの数はt[r-1]
Buggy python submission (verdict: Runtime Error):
S = input()
ans = 0

N = len(S)
Slist = []

for i in range(N):
    Slist.append(S[i])

def f(A, ans):
    n = len(A)
    if n == 0 or n == 1:
        print(ans)
        return 0
        
    for j in range(n-1):
        if A[j] == '0' and A[j+1] == '1':
            del A[j:j+2]
            ans += 2
            break
        elif A[j] == '1' and A[j+1] == '0':
            del A[j:j+2]
            ans += 2
            break
        if j == n-2:
            print(ans)
            return 0 
    f(A, ans)

f(Slist, ans)

        

Fixed submission:
S = input()


N = len(S)

count_0 = 0
count_1 = 0

for i in range(N):
    if S[i] == '0':
        count_0 += 1
    else:
        count_1 += 1

if count_0 > count_1:
    print(int(count_1*2))

else:
    print(int(count_0*2))
Buggy python submission (verdict: Time Limit Exceeded):
i=0
a,b,c,d=map(int,input().split())
while(a!=0 and c!=0):
   if(i%2):
        a-=d
   else:
       c-=b
   i+=1
print("Yes" if a!=0 else "No")

Fixed submission:
ok=True
i=0
a,b,c,d=map(int,input().split())
k=c//b
c-=b*k
a-=d*(k)
if(a<=0 and c!=0):
    print("No")
else:
    print("Yes")
Buggy python submission (verdict: Runtime Error):
s = input()

sum = 0
for bit in range(1 << (len(s) - 1)):
    expr = s
    ins = 0
    for i in range(len(s) - 1):
        ins += i
        if bit & 1 << i:
            expr = expr[:ins+1] + '+' + expr[ins+1:]
            ins += 1
    sum += eval(expr)

print(sum)


Fixed submission:
s = input()

sum = 0
for bit in range(1 << (len(s) - 1)):
    expr = s[0]
    for i in range(len(s) - 1):
        if bit & 1 << i:
            expr += '+'
        expr += s[i + 1]
    sum += eval(expr)

print(sum)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

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

num = []

for i in range(n):
    num.append((i+1)-a[i])

ans = 0
for i in range(n):
    scan = (i+1) + a[i]
    ans += num.count(scan)

print(ans)

Fixed submission:
from collections import Counter

n = int(input())

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

num = []

for i in range(n):
    num.append((i+1)-a[i])

ct = Counter(num)

ans = 0
for i in range(n):
    scan = (i+1) + a[i]
    if(ct[scan] != 0):
        ans += ct[scan]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

a = list(map(int,input().split()))
g = max(a)
num = []
ans = 0
for i in range(n):
    value = a[i]
    if value >= n - (i+1):
        continue
    cnt = 1
    for j in range((i+value+1),n):
        if cnt == a[j] :
            ans += 1
        elif cnt > g:
            break
        cnt += 1

print(ans)

Fixed submission:
from collections import Counter

n = int(input())

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

num = []

for i in range(n):
    num.append((i+1)-a[i])

ct = Counter(num)

ans = 0
for i in range(n):
    scan = (i+1) + a[i]
    if(ct[scan] != 0):
        ans += ct[scan]

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

for i in range(n):
    print(a.count(i+1))

Fixed submission:
from collections import Counter

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

c = Counter(a)
for i in range(1,n+1):
    print(c[i])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = [input() for i in range(n)]

lg = set(s)

check = []
max_qua = 0

for i in lg:
    if(max_qua < s.count(i)):
        max_qua = s.count(i)
        check = [i]
    elif(max_qua == s.count(i)):
        check.append(i)

check = sorted(check)

for i in range(len(check)):
    print(check[i])

Fixed submission:
import collections
n = int(input())
s = [input() for i in range(n)]
p = collections.Counter(s)
res = sorted(p.items(), key=lambda x: x[1],reverse = True)
 
keys = []
#keys = [i for i,m in p.items() if m == p.values()]
u = max(p.values())
for i,m in res:
  if(m == u):
    keys.append(i)
  else:
    break
keys=sorted(keys)
for i in range(len(keys)):
  print(keys[i])

Buggy python submission (verdict: Time Limit Exceeded):
import collections
n = int(input())
s = [input() for i in range(n)]
p = collections.Counter(s)
res = sorted(p.items(), key=lambda x: x[1],reverse = True)

keys = []
#keys = [i for i,m in p.items() if m == p.values()]
for i,m in res:
  if(m == max(p.values())):
    keys.append(i)
  else:
    break
keys=sorted(keys)
for i in range(len(keys)):
  print(keys[i])

Fixed submission:
import collections
n = int(input())
s = [input() for i in range(n)]
p = collections.Counter(s)
res = sorted(p.items(), key=lambda x: x[1],reverse = True)
 
keys = []
#keys = [i for i,m in p.items() if m == p.values()]
u = max(p.values())
for i,m in res:
  if(m == u):
    keys.append(i)
  else:
    break
keys=sorted(keys)
for i in range(len(keys)):
  print(keys[i])

Buggy python submission (verdict: Time Limit Exceeded):
import collections
n = int(input())
s = [input() for i in range(n)]
p = collections.Counter(s)
keys = []
#keys = [i for i,m in p.items() if m == p.values()]
for i,m in p.items():
  if(m == max(p.values())):
    keys.append(i)
keys=sorted(keys)
for i in range(len(keys)):
  print(keys[i])

Fixed submission:
import collections
n = int(input())
s = [input() for i in range(n)]
p = collections.Counter(s)
res = sorted(p.items(), key=lambda x: x[1],reverse = True)
 
keys = []
#keys = [i for i,m in p.items() if m == p.values()]
u = max(p.values())
for i,m in res:
  if(m == u):
    keys.append(i)
  else:
    break
keys=sorted(keys)
for i in range(len(keys)):
  print(keys[i])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
n = int(input())
a = list(map(int,input().split()))
cnt = 0
for i in range(n):
  for j in range((i + 1),n):
    if(a[i] == a[j]):
      print("NO")
      sys.exit()
print("YES")

Fixed submission:
import sys
n = int(input())
a = list(map(int,input().split()))
if(len(a) != len(set(a))):
	print("NO")
else:
  	print("YES")
Buggy python submission (verdict: Time Limit Exceeded):
h = int(input())
temp = 1
ans = 1
cnt = 0
while(True):
  h = h // 2
  cnt += 1
  if(cnt != 1):
  	temp *= 2
  	ans += temp
  if(h == 1):
    break
print(ans + 2**cnt)

Fixed submission:
h = int(input())
if(h == 1):
  print(1)
  exit()
cnt = 1
point = 0
list = [0 for i in range(100)]
while (h>point+1):
  list[cnt] = ((list[cnt-1] * 2) +1)
  point += 2**cnt
  cnt += 1

print(list[cnt-1]*2+1)

Buggy python submission (verdict: Time Limit Exceeded):
h = int(input())
temp = 1
cnt = 0
while(True):
  h = h // 2
  cnt += 1
  if(h == 1):
    break
ans = 1
for i in range(cnt-1):
  temp *= 2
  ans +=temp
  #print(ans)
print(ans + 2**cnt)	
  

Fixed submission:
h = int(input())
if(h == 1):
  print(1)
  exit()
cnt = 1
point = 0
list = [0 for i in range(100)]
while (h>point+1):
  list[cnt] = ((list[cnt-1] * 2) +1)
  point += 2**cnt
  cnt += 1

print(list[cnt-1]*2+1)
Buggy python submission (verdict: Runtime Error):
h,w,n=[input() for i in range(3)]
n = int(n)
w = int(w)
h = int(h)
if(h >= w):
  temp = h
elif(w > h):
  temp = w
temp = (n // temp)
if(n % temp != 0):
    temp = temp + 1
print(temp)

Fixed submission:
h,w,n=[input() for i in range(3)]
n = int(n)
w = int(w)
h = int(h)
if(h >= w):
  temp = h
elif(w > h):
  temp = w
if(n % temp != 0):
  temp = (n // temp)
  temp = temp + 1
else:
  temp = (n // temp)
print(temp)

Buggy python submission (verdict: Runtime Error):
h,w,n=[input() for i in range(3)]
n = int(n)
w = int(w)
h = int(h)
if(h >= w):
  temp = h
else:
  temp = w
temp = (n // temp)
if(n % temp != 0):
	temp = temp + 1
print(temp)


Fixed submission:
h,w,n=[input() for i in range(3)]
n = int(n)
w = int(w)
h = int(h)
if(h >= w):
  temp = h
elif(w > h):
  temp = w
if(n % temp != 0):
  temp = (n // temp)
  temp = temp + 1
else:
  temp = (n // temp)
print(temp)
Buggy python submission (verdict: Runtime Error):
from collections import deque

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

p = deque()

for i in list:
  p.append([i[0] - i[1],i[0] + i[1]])
  
p = sorted(p,key = lambda x: x[1])

ex = []
ex.append(p.pop(left))




for i in range(len(p)):
  if(ex[-1][1] <= p[0][0]):
    ex.append(p.pop(left))
  else:
    p.pop(left)

print(len(ex))

Fixed submission:
from collections import deque

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

p = deque()

for i in list:
  p.append([i[0] - i[1],i[0] + i[1]])
  
p = sorted(p,key = lambda x: x[1])

ex = []
ex.append(p.pop(0))




for i in range(len(p)):
  if(ex[-1][1] <= p[0][0]):
    ex.append(p.pop(0))
  else:
    p.pop(0)

print(len(ex))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
list = [list(map(int,input().split())) for i in range(n)]

p = []

for i in list:
  p.append([i[0] - i[1],i[0] + i[1]])
  
p = sorted(p,key = lambda x: x[1])

ex = []
ex.append(p.pop(0))



for i in range(len(p)):
  if(ex[-1][1] <= p[0][0]):
    ex.append(p.pop(0))
  else:
    p.pop(0)

print(len(ex))

Fixed submission:
from collections import deque

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

p = deque()

for i in list:
  p.append([i[0] - i[1],i[0] + i[1]])
  
p = sorted(p,key = lambda x: x[1])

ex = []
ex.append(p.pop(0))




for i in range(len(p)):
  if(ex[-1][1] <= p[0][0]):
    ex.append(p.pop(0))
  else:
    p.pop(0)

print(len(ex))
Buggy python submission (verdict: Time Limit Exceeded):
def copy(l):
    l1=[]
    for i in l:
        l1.append(i)
    return l1
s = input()
n = len(s)
l = [1]*n
k = 0
c = 1
for i in range(len(s)-1):
    if k<c:
        k = c
    if(s[i+1]==s[i]):
        c+=1
    else:
        c = 0
    
if k%2 ==1:
    k+=1
for _ in range(k):
    l1 = copy(l)
    for i in range(n):
        if(l[i]):
            if s[i] == 'R':
                l[i+1]+=l1[i]
                l[i] =l[i]- l1[i];
            else:
                l[i-1]+=l1[i]
                l[i] =l[i] -l1[i]

for i in l:
    print(i,end = " ")

Fixed submission:
s = input()+'R'
n = len(s)
flag = 0
cr=1
cl=0
l=[]
for i in range(1,n):
    if(s[i]=='L'):
        flag=1
        cl+=1
    elif s[i]=='R' and flag == 0:
        cr+=1
    elif i==n-1 or s[i]=='R' and flag!=0:
        temp = [0]*(cl+cr)
        if(cr>cl):
            diff = cr-cl
            temp[cr-1] = cl+diff-diff//2
            temp[cr] = cl + diff//2
            if (cl+diff-1)%2==1:
                temp[cr-1],temp[cr] = temp[cr],temp[cr-1]
        elif(cr<cl):
            diff = cl-cr
            temp[cr-1] = cr+diff-diff//2
            temp[cr] = cr + diff//2
            if (cr+diff-1)%2==0:
                temp[cr-1],temp[cr] = temp[cr],temp[cr-1]
        else:                #cr==cl
            temp[cr-1] = cr
            temp[cr] = cl  #cr==cl
        l+=temp
        flag = 0
        cr = 1
        cl=0
        #continue
    
print(" ".join(map(str,l)))
Buggy python submission (verdict: Runtime Error):
print(int(eval(input().replace(" ","*")))

Fixed submission:
l = input()
l = l.replace('.', " ")
# print(l)
l = [int(i) for i in l.split()]
a, b, c = l
# print(l)
b = b * 100 + c
a *= b
a //= 100
print(a)
Buggy python submission (verdict: Runtime Error):
a = int(input())
b = int(input())
c = int(input())
print((a+b)*h//2)

Fixed submission:
a = int(input())
b = int(input())
c = int(input())
print((a+b)*c//2)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

ans = 1
for a in ans:
  if ans >= 10**(18)/a:
	ans = -1
    break
  else:
    ans *= a

if 0 in A:
  print(0)
else:
  print(ans)

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

ans = 1
for a in A:
  if ans > 10**(18)//a:
    ans = -1
    break
  else:
    ans *= a

if 0 in A:
  print(0)
else:
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, S = map(int, input().split())
A = list(map(int, input().split()))

MOD = 998244353

def solution(A, S):
    N = len(A)
    
    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(1, N+1):
        for j in range(S+1):
            dp[i][j] += 2*dp[i-1][j]
            dp[i][j] %= MOD
            if j >= A[i-1]:
                dp[i][j] += dp[i-1][j-A[i-1]]
                dp[i][j] %= MOD
    return dp[N][S]

print(solution(A, S))

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

MOD = 998244353

def solution(A, S):
    N = len(A)
    
    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(1, N+1):
        for j in range(S+1):
            dp[i][j] += 2*dp[i-1][j]
            dp[i][j] %= MOD
            if j >= A[i-1]:
                dp[i][j] += dp[i-1][j-A[i-1]]
                dp[i][j] %= MOD
    return dp[N][S]

print(solution(A, S))
Buggy python submission (verdict: Runtime Error):
N = int(input())
st = set()
for _ in range(N):
  S = input()
  st.insert(S)

print(len(st))

Fixed submission:
N = int(input())
st = set()
for _ in range(N):
  S = input()
  st.add(S)

print(len(st))
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = list(map(int, input().split())
         
print(max(-1, N-sum(A)))

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

print(max(-1, N-sum(A)))
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split())

num_subordinates = [0 for _ in N]
for a in A:
	++num_subordinates[a]

for n in num_subordinates:
	print(n)

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

num_subordinates = [0 for _ in range(N)]
for a in A:
	num_subordinates[a-1] += 1

for n in num_subordinates:
	print(n)
Buggy python submission (verdict: Runtime Error):
S, T = input().split
print(T, S, sep='')

Fixed submission:
S, T = input().split()
print(T, S, sep='')
Buggy python submission (verdict: Runtime Error):
A, B, K = map(int, input().split())

print(max(0, A-K), max(0, B-max(0, K-A))

Fixed submission:
A, B, K = map(int, input().split())

print(max(0, A-K), max(0, B-max(0, K-A)))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

ans = 0
for p in range(1000):
  s = '{:03}'.format(p)
  i = 0
  for j in range(N):
    if i < 3 and S[j] == s[i]:
      i += 1
  if i == 3:
    ans += 1
print(ans)


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

ans = 0
for p in range(1000):
  s = '{:03}'.format(p)
  i = 0
  for j in range(N):
    if i < 3 and S[j] == s[i]:
      i += 1
  if i == 3:
    ans += 1
print(ans)

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

ans = 0
for p in range(1000):
  s = '{:03}'.format(p)
  i = 0
  for j in range(N):
    if i < 3 and S[j] == s[i]:
      i += 1
  	if i== 3:
      ans += 1
print(ans)

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

ans = 0
for p in range(1000):
  s = '{:03}'.format(p)
  i = 0
  for j in range(N):
    if i < 3 and S[j] == s[i]:
      i += 1
  if i == 3:
    ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(1, N+1):
  w, v = map(int, input().split())
  for j in range(W+1):
    dp[i][j] = dp[i-1][j]
    if j >= w:
      dp[i][j] = max(dp[i][j], dp[i-1][j-w]+v)

print(dp[N][W])

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

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(1, N+1):
  w, v = map(int, input().split())
  for j in range(W+1):
    dp[i][j] = dp[i-1][j]
    if j >= w:
      dp[i][j] = max(dp[i][j], dp[i-1][j-w]+v)

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

MAX_V = 10**5
dp = [[10**(18)]*(MAX_V+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
  w, v = map(int, input().split())
  for j in range(MAX_V+1):
    dp[i][j] = dp[i-1][j]
    if j >= v:
      dp[i][j] = min(dp[i][j], dp[i-1][j-v]+w)

ans = 0
for j in range():
  if dp[N][j] <= W and dp[N][j] != 10**(18):
    ans = max(ans, j)
print(ans)

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

MAX_V = 10**5
dp = [[10**(18)]*(MAX_V+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
  w, v = map(int, input().split())
  for j in range(MAX_V+1):
    dp[i][j] = dp[i-1][j]
    if j >= v:
      dp[i][j] = min(dp[i][j], dp[i-1][j-v]+w)

ans = 0
for j in range(MAX_V+1):
  if dp[N][j] <= W and dp[N][j] != 10**(18):
    ans = max(ans, j)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int, input().split()))

# dp[i][j] = a[i:j] を考えたときの X-Y の最大値
dp = [[0]*(N+1) for _ in range(N+1)]
for l in range(1, N+1):
    for i in range(N-l+1):
        j = i+l
        if (N-l)%2 == 0:
            dp[i][j] = max(dp[i+1][j]+a[i], dp[i][j-1]+a[j-1])
        else:
            dp[i][j] = min(dp[i+1][j]-a[i], dp[i][j-1]-a[j-1])
        
print(dp[0][N])

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

# dp[i][j] = a[i:j] を考えたときの X-Y の最大値
dp = [[0]*(N+1) for _ in range(N+1)]
for l in range(1, N+1):
    for i in range(N-l+1):
        j = i+l
        if (N-l)%2 == 0:
            dp[i][j] = max(dp[i+1][j]+a[i], dp[i][j-1]+a[j-1])
        else:
            dp[i][j] = min(dp[i+1][j]-a[i], dp[i][j-1]-a[j-1])
        
print(dp[0][N])
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9 + 7

N = int(input())
s = input()

# dp[i][j] := i 番目まで決めて i 番目の数より大きいものが j 個のときの場合の数
dp = [[0]*N for _ in range(N)]
dp[0] = [1]*(N+1)
for i in range(N-1):
    # 累積和をとっておく
    # for j in range(N-1):
    #     dp[i][j+1] += dp[i][j]
    for j in range(N-i-1):
        if s[i] == '<':
            for k in range(j+1, N-i):
                dp[i+1][j] += dp[i][k]
        else:
            for k in range(j+1):
                dp[i+1][j] += dp[i][k]
        dp[i+1][j] %= MOD

print(dp[N-1][0])

Fixed submission:
MOD = 10**9 + 7

N = int(input())
s = input()

# dp[i][j] := i 番目まで決めて i 番目の数より大きいものが j 個のときの場合の数
dp = [[0]*N for _ in range(N)]
dp[0] = [1]*(N+1)
for i in range(N-1):
    # 累積和をとっておく
    for j in range(N-1):
        dp[i][j+1] += dp[i][j]
    for j in range(N-i-1):
        if s[i] == '<':
            dp[i+1][j] += dp[i][N-i-1]-dp[i][j]
        else:
            dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD

print(dp[N-1][0])