Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
n,p = map(int, input().split())
s = input()

if p==2 or p==5:
    res = 0
    for i in range(n-1,-1,-1):
        if int(s[i])%p==0:
            res += i+1
    print(res)
    exit()

u = defaultdict(int)
u[0] = 1
for i in range(n):
    d = int(s[i:])
    u[d%p] += 1

res = 0
for v in u.values():
    res += v*(v-1)//2

print(res)

Fixed submission:
from collections import defaultdict
n,p = map(int, input().split())
s = input()

if p==2 or p==5:
    res = 0
    for i in range(n-1,-1,-1):
        if int(s[i])%p==0:
            res += i+1
    print(res)
    exit()

u = defaultdict(int)
u[0] = 1
f = 1
d = 0
for i in range(n-1,-1,-1):
    d = (d + int(s[i])*f)%p
    f = (f*10)%p
    u[d%p] += 1

res = 0
for v in u.values():
    res += v*(v-1)//2

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
h,n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

inf = 10**9
dp = [[inf]*(h+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(h+1):
        k = 0
        while ab[i][0]*k<=h:
            d = j+ab[i][0]*k
            dp[i+1][min(h,d)] = min(dp[i+1][min(h,d)], dp[i][j]+ab[i][1]*k)
            k += 1
        d = j+ab[i][0]*k
        dp[i+1][min(h,d)] = min(dp[i+1][min(h,d)], dp[i][j]+ab[i][1]*k)

res = dp[n][h]
print(res)

Fixed submission:
# -*- coding: utf-8 -*-
h,n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

inf = 10**9
dp = [inf]*(h+1)
dp[0] = 0
for i in range(n):
    for j in range(h+1):
        d = min(j+ab[i][0], h)
        dp[d] = min(dp[d], dp[j]+ab[i][1])

res = dp[h]
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
n = int(input())
al = list(map(int, input().split()))


# GCD
def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def lcm(a,b):
    return a*b//gcd(a,b)

def lcmlist(l):
    res = l[0]
    for x in l[1:]:
        res = lcm(res, x)
    return res

l = lcmlist(al)
res = 0
for a in al:
    res += l//a
    res %= 10**9+7

print(res)

Fixed submission:
# -*- coding: utf-8 -*-
n = int(input())
al = list(map(int, input().split()))
MOD = 10**9 + 7

# aのmod Mでの逆元
def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t*v
        u,v = v,u
    u %= m
    if u<0:
        u += m
    return u

# GCD
def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def lcm(a,b):
    return a*b//gcd(a,b)

def lcmlist(l):
    res = l[0]
    for x in l[1:]:
        res = lcm(res, x)
    return res

l = lcmlist(al)%MOD
res = 0
for a in al:
    res += l*modinv(a,MOD)
    res %= MOD

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
n = int(input())
al = list(map(int, input().split()))


# GCD
def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def lcm(a,b):
    return a*b//gcd(a,b)

def lcmlist(l):
    res = l[0]
    for x in l[1:]:
        res = lcm(res, x)
    return res

l = lcmlist(al)
res = 0
for a in al:
    res += l//a
    res %= 10**9+7

print(res)

Fixed submission:
# -*- coding: utf-8 -*-
n = int(input())
al = list(map(int, input().split()))
MOD = 10**9 + 7

# aのmod Mでの逆元
def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t*v
        u,v = v,u
    u %= m
    if u<0:
        u += m
    return u

# GCD
def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def lcm(a,b):
    return a*b//gcd(a,b)

def lcmlist(l):
    res = l[0]
    for x in l[1:]:
        res = lcm(res, x)
    return res

l = lcmlist(al)%MOD
res = 0
for a in al:
    res += l*modinv(a,MOD)
    res %= MOD

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = list(input())

def check(pin):
    i = 0
    pi = 0
    while i<n and pi<3:
        if s[i]==pin[pi]:
            pi += 1
        i += 1
    return pi==3

res = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            if check(str(i)+str(j)+str(k)):
                res += 1

print(res)

Fixed submission:
n = int(input())
s = list(input())

d = [[] for _ in range(10)]
for i in range(n):
    d[int(s[i])].append(i)

def lower_bound(al,k):
    if len(al)==0:
        return -1
    ng = -1
    ok = len(al)
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if al[mid]>k:
            ok = mid
        else:
            ng = mid
    if ok==len(al):
        return -1
    return ok

def check(pl):
    pos = -1
    res = []
    for i in range(3):
        pos = lower_bound(d[pl[i]], pos)
        if pos<0:
            return False
        pos = d[pl[i]][pos]
        res.append(pos)
    return True

res = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            if check([i,j,k]):
                res += 1

print(res)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**5+10)

n = int(input())
visited = set()
g = {}
idx = {}
color = {}
for i in range(n-1):
    a,b = map(int, input().split())
    idx[i] = (a,b)
    if a not in g:
        g[a] = []
    g[a].append(b)
    if b not in g:
        g[b] = []
    g[b].append(a)

def dfs(v,c):
    cc = 0
    for u in g[v]:
        if u in visited:
            continue
        visited.add(u)

        cc += 1
        while cc==c:
            cc += 1
        a,b = min(u,v),max(u,v)
        color[(a,b)] = cc
        
        dfs(u,cc)
visited.add(1)
dfs(1,0)

print(max(*color.values()))
for i in range(n-1):
    print(color[idx[i]])

Fixed submission:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**5+10)

n = int(input())
visited = set()
g = {}
idx = {}
color = {}
for i in range(n-1):
    a,b = map(int, input().split())
    idx[i] = (a,b)
    if a not in g:
        g[a] = []
    g[a].append(b)
    if b not in g:
        g[b] = []
    g[b].append(a)

def dfs(v,c):
    cc = 0
    for u in g[v]:
        if u in visited:
            continue
        visited.add(u)

        cc += 1
        while cc==c:
            cc += 1
        a,b = min(u,v),max(u,v)
        color[(a,b)] = cc
        
        dfs(u,cc)
visited.add(1)
dfs(1,0)

mc = 0
for c in color.values():
    mc = max(mc, c)
print(mc)
for i in range(n-1):
    print(color[idx[i]])
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

def bsearch(l,n,k):
    ok = -1
    ng = n

    while ng-ok>1:
        mid = (ng+ok)//2
        if l[mid]<k:
            ok = mid
        else:
            ng = mid
    return ok

def f(l):
    n = len(l)
    l.sort()

    res = 0
    for i in range(n-1):
        for j in range(i+1,n):
            k = bsearch(l,n,l[i]+l[j])
            res += k-j

    return res

if __name__ == '__main__':
    n = int(input())
    l = list(map(int, input().split()))
    print(f(l))



Fixed submission:
# -*- coding: utf-8 -*-

def bsearch(l,n,k):
    ok = -1
    ng = n

    while ng-ok>1:
        mid = (ng+ok)//2
        if l[mid]<k:
            ok = mid
        else:
            ng = mid
    return ok

def f(l):
    n = len(l)
    l.sort()

    res = 0
    for i in range(n-1):
        for j in range(i+1,n):
            k = bsearch(l,n,l[i]+l[j])
            res += k-j

    return res

if __name__ == '__main__':
    n = int(input())
    l = list(map(int, input().split()))
    print(f(l))
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
from math import sqrt
a,b = map(int, input().split())

sa = set([1])
i = 2
while a>1:
    while a%i==0:
        sa.add(i)
        a //= i
    i += 1

sb = set([1])
i = 2
while b>1:
    while b%i==0:
        sb.add(i)
        b //= i
    i += 1

print(len(sa & sb))

Fixed submission:
# -*- coding: utf-8 -*-
from math import sqrt
a,b = map(int, input().split())
xa,xb = a,b

sa = set([1])
i = 2
while a>1:
    if i>sqrt(xa):
        sa.add(a)
        break
    while a%i==0:
        sa.add(i)
        a //= i
    i += 1

sb = set([1])
i = 2
while b>1:
    if i>sqrt(xb):
        sb.add(b)
        break
    while b%i==0:
        sb.add(i)
        b //= i
    i += 1

print(len(sa & sb))

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
from math import sqrt
a,b = map(int, input().split())

sa = set([1])
i = 2
while a>1:
    while a%i==0:
        sa.add(i)
        a //= i
    i += 1

sb = set([1])
i = 2
while b>1:
    while b%i==0:
        sb.add(i)
        b //= i
    i += 1

print(len(sa & sb))

Fixed submission:
# -*- coding: utf-8 -*-
from math import sqrt
a,b = map(int, input().split())
xa,xb = a,b

sa = set([1])
i = 2
while a>1:
    if i>sqrt(xa):
        sa.add(a)
        break
    while a%i==0:
        sa.add(i)
        a //= i
    i += 1

sb = set([1])
i = 2
while b>1:
    if i>sqrt(xb):
        sb.add(b)
        break
    while b%i==0:
        sb.add(i)
        b //= i
    i += 1

print(len(sa & sb))
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int, input().split())
l = []
for _ in range(m):
    a,b = map(int, input().split())
    cl = [x-1 for x in map(int, input().split())]
    b = 0
    for i in cl:
        b |= 1<<i
    l.append([a,b])

inf = 10**9
dp = [inf]*2**n
dp[0] = 0
for x in range(2**n):
    for i in range(m):
        a,b = l[i]
        dp[x|b] = min(dp[x|b], dp[x]+a)

if dp[-1]==inf:
    print(-1)
else:
    print(dp[-1])

Fixed submission:
n,m = map(int, input().split())
l = []
for _ in range(m):
    a,b = map(int, input().split())
    cl = [x-1 for x in map(int, input().split())]
    b = 0
    for i in cl:
        b |= 1<<i
    l.append([a,b])

inf = 10**9
dp = [inf]*2**n
dp[0] = 0
for x in range(2**n):
    for i in range(m):
        a,b = l[i]
        dp[x|b] = min(dp[x|b], dp[x]+a)

if dp[-1]==inf:
    print(-1)
else:
    print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

n = int(input())
s = input()

for m in range(n//2+1,0,-1):
    d = {}
    for l in range(n-m+1):
        ss = s[l:l+m]
        if ss not in d:
            d[ss] = l
        else:
            l2 = d[ss]
            if l2+m<=l:
                print(m)
                exit()
print(0)


Fixed submission:
# -*- coding: utf-8 -*-

n = int(input())
s = input()

ok = 0
ng = n//2+1

while ng-ok>1:
    mid = (ok+ng)//2

    d = {}
    isOk = False
    for l in range(n-mid+1):
        ss = s[l:l+mid]
        if ss not in d:
            d[ss] = l
        else:
            l2 = d[ss]
            if l2+mid<=l:
                isOk = True
                break

    if isOk:
        ok = mid
    else:
        ng = mid

print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

n = int(input())
s = input()

for m in range(n//2+1,0,-1):
    d = {}
    for l in range(n-m+1):
        ss = s[l:l+m]
        if ss not in d:
            d[ss] = l
        else:
            l2 = d[ss]
            if l2+m<=l:
                print(m)
                exit()
print(0)


Fixed submission:
# -*- coding: utf-8 -*-

n = int(input())
s = input()

ok = 0
ng = n//2+1

while ng-ok>1:
    mid = (ok+ng)//2

    d = {}
    isOk = False
    for l in range(n-mid+1):
        ss = s[l:l+mid]
        if ss not in d:
            d[ss] = l
        else:
            l2 = d[ss]
            if l2+mid<=l:
                isOk = True
                break

    if isOk:
        ok = mid
    else:
        ng = mid

print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
n = int(input())
s = input()

d = {}
res = 0
for l1 in range(n):
    for l2 in range(l1+1,n+1):
        ss = s[l1:l2]
        if ss not in d:
            d[ss] = l1
        else:
            if d[ss]+len(ss)<=l1:
                res = max(res,len(ss))
print(res)


Fixed submission:
# -*- coding: utf-8 -*-

n = int(input())
s = input()

ok = 0
ng = n//2+1

while ng-ok>1:
    mid = (ok+ng)//2

    d = {}
    isOk = False
    for l in range(n-mid+1):
        ss = s[l:l+mid]
        if ss not in d:
            d[ss] = l
        else:
            l2 = d[ss]
            if l2+mid<=l:
                isOk = True
                break

    if isOk:
        ok = mid
    else:
        ng = mid

print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
n = int(input())
s = input()

d = {}
res = 0
for l1 in range(n):
    for l2 in range(l1+1,n+1):
        ss = s[l1:l2]
        if ss not in d:
            d[ss] = l1
        else:
            if d[ss]+len(ss)<=l1:
                res = max(res,len(ss))
print(res)


Fixed submission:
# -*- coding: utf-8 -*-

n = int(input())
s = input()

ok = 0
ng = n//2+1

while ng-ok>1:
    mid = (ok+ng)//2

    d = {}
    isOk = False
    for l in range(n-mid+1):
        ss = s[l:l+mid]
        if ss not in d:
            d[ss] = l
        else:
            l2 = d[ss]
            if l2+mid<=l:
                isOk = True
                break

    if isOk:
        ok = mid
    else:
        ng = mid

print(ok)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
s = input()
n = len(s)
t = input()
m = len(t)

d = {}
for c in t:
    if c in d:
        continue
    else:
        d[c] = []
    for i in range(2*n):
        if s[i%n]==c:
            d[c].append(i)

res = -1
for i in range(m):
    c = t[i]
    if len(d[c])==0:
        print(-1)
        exit()

    j = 0
    while res%n>=d[c][j]:
        j += 1
    res += d[c][j] - res%n

print(res+1)


Fixed submission:
# -*- coding: utf-8 -*-

def lower_bound(l,k):
    def isOk(i):
        return l[i]>k

    ok = len(l)
    ng = -1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2

        if isOk(mid):
            ok = mid
        else:
            ng = mid
    return ok

s = input()
n = len(s)
t = input()
m = len(t)

d = {}
for c in t:
    if c in d:
        continue
    else:
        d[c] = []
    for i in range(2*n):
        if s[i%n]==c:
            d[c].append(i)
res = -1
for i in range(m):
    c = t[i]
    if len(d[c])==0:
        print(-1)
        exit()

    j = lower_bound(d[c],res%n)
    res += d[c][j] - res%n

print(res+1)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
MOD = 10**9+7
s = input()
n = len(s)

dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
b = 1
for i in range(1,n+1):
    if s[n-i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i][(j*b+k)%13] += dp[i-1][k]
    else:
        j = int(s[n-i])
        for k in range(13):
            dp[i][(j*b+k)%13] += dp[i-1][k]
    for k in range(13):
        dp[i][k] %= MOD
    b *= 10
    b %= 13

print(dp[n][5]%MOD)

Fixed submission:
# -*- coding: utf-8 -*-
MOD = 10**9+7
s = input()
n = len(s)

dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
b = 1
for i in range(1,n+1):
    if s[n-i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i][(j*b+k)%13] += dp[i-1][k]
    else:
        j = int(s[n-i])
        for k in range(13):
            dp[i][(j*b+k)%13] += dp[i-1][k]
    for k in range(13):
        dp[i][k] %= MOD
    b *= 10
    b %= 13

print(dp[n][5]%MOD)
Buggy python submission (verdict: Runtime Error):
n = int(input())
al = list(map(int, input().split()))
al.sort()

res = []
neg = []
pos = []
for a in al:
    if a>=0:
        pos.append(a)
    else:
        neg.append(a)

if len(pos)==0:
    res.append((neg[0],neg[1]))
    pos.append(neg[0]-neg[1])
    neg = neg[2:]
if len(neg)==0:
    res.append((pos[0],pos[1]))
    neg.append(pos[0]-pos[1])
    pos = pos[2:]


# len(pos)>0 and len(neg)>0
n = neg[0]
for i in range(1,len(pos)):
    res.append((n,pos[i]))
    n = n - pos[i]
p = pos[0]
for i in range(1,len(neg)):
    res.append((p,neg[i]))
    p = p - neg[i]
res.append((p,n))
print(p-n)
for x,y in res:
    print(x,y)

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

if n==2:
    print(max(al)-min(al))
    print(max(al),min(al))
    exit()

pos = []
neg = []
for a in al:
    if a>=0:
        pos.append(a)
    else:
        neg.append(a)

pos.sort()
neg.sort(reverse=True)
res = []

if len(pos)==0:
    x = neg[0]
    for a in neg[1:]:
        res.append((x,a))
        x -= a
elif len(neg)==0:
    x = pos[0]
    for a in pos[1:-1]:
        res.append((x,a))
        x -= a
    res.append((pos[-1],x))
    x = pos[-1]-x
else:
    p = pos[0]
    pos = pos[1:]

    x = neg[0]
    neg = neg[1:]

    for a in pos:
        res.append((x,a))
        x -= a
    res.append((p,x))
    x = p - x
    for a in neg:
        res.append((x,a))
        x -= a


print(x)
for a,b in res:
    print(a,b)
Buggy python submission (verdict: Runtime Error):
from operator import itemgetter

n,m = map(int, input().split())
al = list(map(int, input().split()))
bc = []
for _ in range(m):
    b,c = map(int, input().split())
    bc.append([b,c])


bc.sort(key=itemgetter(1), reverse=True)
al.sort()

i = 0
while len(bc)>0 and i<n:
    b,c = bc.pop(0)

    for j in range(b):
        if al[i+j]<c:
            al[i+j] = c
    i += b

print(sum(al))

Fixed submission:
from operator import itemgetter

n,m = map(int, input().split())
al = list(map(int, input().split()))
bc = []
for _ in range(m):
    b,c = map(int, input().split())
    bc.append([b,c])


bc.sort(key=itemgetter(1), reverse=True)
al.sort()

i = 0
while len(bc)>0 and i<n:
    b,c = bc.pop(0)

    for j in range(b):
        if i+j<n and al[i+j]<c:
            al[i+j] = c
    i += b

print(sum(al))
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
n = int(input())
sl = [input() for _ in range(n)]

xa = []
bx = []
ba = []
x = []
for s in sl:
    if s[0]=="B" and s[-1]=="A":
        ba.append(s)
    elif s[-1]=="A":
        xa.append(s)
    elif s[0]=="B":
        bx.append(s)
    else:
        x.append(s)
xa = xa[:-1]+[xa[-1]+"".join(ba)]

if len(xa)>=len(bx):
    for i in range(len(bx)):
        x.append(xa[i]+bx[i])
    x = x+xa[len(bx):]
else:
    for i in range(len(xa)):
        x.append(xa[i]+bx[i])
    x = x+bx[len(xa):]

res = "".join(x)
print(res.count("AB"))


Fixed submission:
# -*- coding: utf-8 -*-
n = int(input())
sl = [input() for _ in range(n)]

xa = []
bx = []
ba = []
x = []
for s in sl:
    if s[0]=="B" and s[-1]=="A":
        ba.append(s)
    elif s[-1]=="A":
        xa.append(s)
    elif s[0]=="B":
        bx.append(s)
    else:
        x.append(s)

if len(xa)>0:
    xa = xa[:-1]+[xa[-1]+"".join(ba)]
elif len(bx)>0:
    bx = bx[:-1]+["".join(ba)+bx[-1]]
else:
    x.append("".join(ba))

if len(xa)>=len(bx):
    for i in range(len(bx)):
        x.append(xa[i]+bx[i])
    x = x+xa[len(bx):]
else:
    for i in range(len(xa)):
        x.append(xa[i]+bx[i])
    x = x+bx[len(xa):]

res = "".join(x)
print(res.count("AB"))

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
n = int(input())
sl = [input() for _ in range(n)]

xa = []
bx = []
ab = []
x = []
for s in sl:
    if s[0]=="B" and s[-1]=="A":
        ab.append(s)
    elif s[-1]=="A":
        xa.append(s)
    elif s[0]=="B":
        bx.append(s)
    else:
        x.append(s)
ab = ["".join(ab)]

if len(ab)>len(bx):
    bx.append(ab[0])
else:
    xa.append(ab[0])

if len(xa)>=len(bx):
    for i in range(len(bx)):
        x.append(xa[i]+bx[i])
    x = x+xa[len(bx):]
else:
    for i in range(len(xa)):
        x.append(xa[i]+bx[i])
    x = x+xb[len(xa):]
res = "".join(x)
print(res.count("AB"))


Fixed submission:
# -*- coding: utf-8 -*-
n = int(input())
sl = [input() for _ in range(n)]

xa = []
bx = []
ba = []
x = []
for s in sl:
    if s[0]=="B" and s[-1]=="A":
        ba.append(s)
    elif s[-1]=="A":
        xa.append(s)
    elif s[0]=="B":
        bx.append(s)
    else:
        x.append(s)

if len(xa)>0:
    xa = xa[:-1]+[xa[-1]+"".join(ba)]
elif len(bx)>0:
    bx = bx[:-1]+["".join(ba)+bx[-1]]
else:
    x.append("".join(ba))

if len(xa)>=len(bx):
    for i in range(len(bx)):
        x.append(xa[i]+bx[i])
    x = x+xa[len(bx):]
else:
    for i in range(len(xa)):
        x.append(xa[i]+bx[i])
    x = x+bx[len(xa):]

res = "".join(x)
print(res.count("AB"))
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
n = int(input())
vl = list(map(int, input().split()))
cl = list(map(int, input().split()))

res = -1

for i in range(2**n):
    x = 0
    y = 0
    for j in range(n):
        if i>>j&1==1:
            x += vl[j]
            y += cl[j]
    res = max(res, x-y)

print(res)


Fixed submission:
# -*- coding: utf-8 -*-
n = int(input())
vl = list(map(int, input().split()))
cl = list(map(int, input().split()))

res = -1

for i in range(2**n):
    x = 0
    y = 0
    for j in range(n):
        if i>>j&1==1:
            x += vl[j]
            y += cl[j]
    res = max(res, x-y)

print(res)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
n,q = map(int, input().split())
s = input()
td = [input().split() for _ in range(q)]

l = 0
r = n - 1
for i in range(q-1,-1,-1):
    t,d = td[i]

    if s[l]==t and d=="L":
        l += 1
    elif l>0 and s[l-1]==t and d=="R":
        l -= 1

    if s[r]==t and d=="R":
        r -= 1
    elif r<n-1 and s[r+1]==t and d=="L":
        r += 1

print(n - l - (n-1-r))


Fixed submission:
# -*- coding: utf-8 -*-
n,q = map(int, input().split())
s = input()
td = [input().split() for _ in range(q)]

def check(idx, x):
    for t,d in td:
        if idx==x:
            return True
        elif idx==n or idx==-1:
            return False

        if s[idx]==t:
            if d=="L":
                idx -= 1
            else:
                idx += 1
    return idx==x

ok = -1
ng = n
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if check(mid, -1):
        ok = mid
    else:
        ng = mid
res = ok+1

ok = n
ng = -1
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if check(mid, n):
        ok = mid
    else:
        ng = mid
res += n-ok

print(n-res)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
n = int(input())

res1 = 0
res2 = 0
for _ in range(n):
    x,u = input().split()
    if u=="JPY":
        res1 += int(x)
    else:
        res2 += float(x)*380000.0

print("{:.8}".format(res1+res2))


Fixed submission:
# -*- coding: utf-8 -*-
from decimal import *
n = int(input())

res1 = Decimal(0)
res2 = Decimal(0)
for _ in range(n):
    x,u = input().split()
    if u=="JPY":
        res1 += Decimal(x)
    else:
        res2 += Decimal(x)*Decimal(380000.0)

print(res1+res2)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
n = int(input())

res = 0
for _ in range(n):
    x,u = input().split()
    if u=="JPY":
        res += int(x)
    else:
        res += float(x)*380000.0

print("{:.8}".format(res))


Fixed submission:
# -*- coding: utf-8 -*-
from decimal import *
n = int(input())

res1 = Decimal(0)
res2 = Decimal(0)
for _ in range(n):
    x,u = input().split()
    if u=="JPY":
        res1 += Decimal(x)
    else:
        res2 += Decimal(x)*Decimal(380000.0)

print(res1+res2)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
num = [0,2,5,5,4,5,6,3,7,6]
#      0,1,2,3,4,5,6,7,8,9
n,m = map(int, input().split())
al = list(map(int, input().split()))

INF = 10**18
dp = [-INF for _ in range(n+1)]
dp[0] = 0

for i in range(1,n+1):
    for a in al:
        if i-num[a]>=0:
            dp[i] = max(dp[i], dp[i-num[a]]+1)

res = []
al.sort(reverse=True)

while n>0:
    for a in al:
        if dp[n-num[a]]==dp[n]-1:
            res.append(str(a))
            n -= num[a]
            break

print("".join(res))


Fixed submission:
# -*- coding: utf-8 -*-
num = [0,2,5,5,4,5,6,3,7,6]
#      0,1,2,3,4,5,6,7,8,9

def f(n,al):
    INF = 10**18
    dp = [-INF for _ in range(n+1)]
    dp[0] = 0

    for i in range(1,n+1):
        for a in al:
            if i-num[a]>=0:
                dp[i] = max(dp[i], dp[i-num[a]]+1)

    res = []
    al.sort(reverse=True)

    while n>0:
        for a in al:
            if n-num[a]>=0 and dp[n-num[a]]==dp[n]-1:
                res.append(str(a))
                n -= num[a]
                break

    return "".join(res)

if __name__ == '__main__':
    n,m = map(int, input().split())
    al = list(map(int, input().split()))
    print(f(n,al))

    # from random import shuffle
    # for _ in range(1000):
    #     n = 10000
    #     m = 5
    #     al = list(range(1,10))
    #     shuffle(al)
    #     al = al[:m]
    #     f(n,al)