Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N,*A=map(int,input().split())
print(max((N//min(A)+4),5))

Fixed submission:
import math
n=int(input())
A=[int(input()) for i in range(5)]
m=min(A)
print(math.ceil(n/m)+4)
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())
    w=s[l-1:r]
    print(w.count('AC'))

Fixed submission:
n,q=map(int, input().split())
s=input()
num_ac=[0 for i in range(n)]
#num_ac[i]はi+1文字目までのACの数？
for i in range(1,n):
    num_ac[i]=num_ac[i-1]
    if s[i]=='C' and s[i-1]=='A':
        num_ac[i]+=1
for i in range(q):
    l,r=map(int,input().split())
    print(num_ac[r-1]-num_ac[l-1])

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())
    w=s[l-1:r]
    print(w.count('AC'))

Fixed submission:
n,q=map(int, input().split())
s=input()
num_ac=[0 for i in range(n)]
#num_ac[i]はi+1文字目までのACの数？
for i in range(1,n):
    num_ac[i]=num_ac[i-1]
    if s[i]=='C' and s[i-1]=='A':
        num_ac[i]+=1
for i in range(q):
    l,r=map(int,input().split())
    print(num_ac[r-1]-num_ac[l-1])
Buggy python submission (verdict: Runtime Error):
from collections import deque
s=input()
d=deque(s)
ans=deque([])
ans.append(d[0])
c=0
for i in range(len(s)):
    if ans==[]:
        ans.append(d[i])
    elif ans[-1]==d[i]:
        ans.append(d[i])
    else:
        ans.pop()
        c+=2
print(c)

Fixed submission:
s=input()
ans=[]
for i in s:
    if ans==[]:
        ans.append(i)
    elif ans[-1]!=i:
        ans.pop()
    else:
        ans.append(i)
print(len(s)-len(ans))
Buggy python submission (verdict: Runtime Error):
A=set(list(map(int,input().split())))
print('YES' if A==set(list(1,9,7,4)) else 'NO')

Fixed submission:
A=list(map(int,input().split()))
L=[1,9,7,4]
print('YES' if set(A)==set(L) else 'NO')
Buggy python submission (verdict: Runtime Error):
s=input()
word='keyence'
basho=0
for i in s:
  if word[basho]==i:
    basho+=1
print('YES' if basho==7 else 'NO')

Fixed submission:
s=input()
word='keyence'
flag=0
if s[:6]==word:
    flag=1
if s[-7:]==word:
    flag=1
for i in range(7):
    if s[:i]+s[-(7-i):]==word:
        flag=1
print('YES' if flag else 'NO')
Buggy python submission (verdict: Time Limit Exceeded):
n,w=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(n)]
#WV[i][0]が重さ、WV[i][1]が価値
#配るDP
dp=[[0 for i in range(w+1)] for i in range(n+1)]
#dp[i][j]はi回目(0,n-1)に重さjまで入るmax value
for i in range(n):
    for j in range(w+1):
        if WV[i][0]+j<=w and i <=n-1:
            dp[i+1][j+WV[i][0]]=max(dp[i][j+WV[i][0]], dp[i][j]+WV[i][1])
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        else:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
print(max(dp[n]))

Fixed submission:
n,w=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(n)]
#WV[i][0]が重さ、WV[i][1]が価値
#配るDP
dp=[[0 for i in range(w+1)] for i in range(n+1)]
#dp[i][j]はi回目(0,n-1)に重さjまで入るmax value
for i in range(n):
    for j in range(w+1):
        if WV[i][0]+j<=w and i <=n-1:
            dp[i+1][j+WV[i][0]]=max(dp[i][j+WV[i][0]], dp[i][j]+WV[i][1])
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        else:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
print(max(dp[n]))
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
s_len = len(s)
t = input()
t_len = len(t)
dp = [[0] * (t_len + 1) for _ in range(s_len + 1)]
for i in range(s_len):
    S = s[i]
    for j in range(t_len):
        T = t[j]
        ni = i + 1
        nj = j + 1
        if S == T:
            dp[ni][nj] = max(dp[ni][nj], dp[i][j] + 1, dp[i][nj], dp[ni][j])
        else:
            dp[ni][nj] = max(dp[ni][nj], dp[i][nj], dp[ni][j])

nagasa = dp[s_len][t_len]

a = s_len
b = t_len
ans = []
while nagasa > 0:
    if dp[a][b] == nagasa:
        a -= 1
    elif dp[a + 1][b] == nagasa:
        b -= 1
    else:
        ans.append(s[a])
        nagasa -= 1
ans = ans[::-1]
print(*ans, sep="")


Fixed submission:
S=input()
T=input()
s=len(S)
t=len(T)
#dp[i][j] Sのi文字目までとTのj文字目までで最大共通文字数
dp=[[0]*(t+1) for i in range(s+1)]
for i in range(s):
    for j in range(t):
        if S[i]==T[j]:
            dp[i+1][j+1]=max(dp[i][j]+1, dp[i][j])
        else:
            dp[i+1][j+1]=max(dp[i+1][j], dp[i][j+1])
ans=''
while s>0 and t>0:
    if dp[s][t]==dp[s-1][t]:
        s-=1
    elif dp[s][t]==dp[s][t-1]:
        t-=1
    else:
        s-=1
        t-=1
        ans+=T[t]
ans=ans[::-1]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
T=input()
s=len(S)
t=len(T)
#dp[i][j] Sのi文字目までとTのj文字目までで最大共通文字数
dp=[[0]*(t+1) for i in range(s+1)]
for i in range(s):
    for j in range(t):
        if S[i]==T[j]:
            dp[i+1][j+1]=max(dp[i][j]+1, dp[i][j])
        else:
            dp[i+1][j+1]=max(dp[i+1][j], dp[i][j+1])
ans=''
while s>0 and t>0:
    if dp[s][t]==dp[s-1][t]:
        s-=1
    elif dp[s][t]==dp[s][t-1]:
        t-=1
    else:
        s-=1
        t-=1
        ans+=T[t]
ans=ans[::-1]
print(ans)

Fixed submission:
S=input()
T=input()
s=len(S)
t=len(T)
#dp[i][j] Sのi文字目までとTのj文字目までで最大共通文字数
dp=[[0]*(t+1) for i in range(s+1)]
for i in range(s):
    for j in range(t):
        if S[i]==T[j]:
            dp[i+1][j+1]=max(dp[i][j]+1, dp[i][j])
        else:
            dp[i+1][j+1]=max(dp[i+1][j], dp[i][j+1])
ans=''
while s>0 and t>0:
    if dp[s][t]==dp[s-1][t]:
        s-=1
    elif dp[s][t]==dp[s][t-1]:
        t-=1
    else:
        s-=1
        t-=1
        ans+=T[t]
ans=ans[::-1]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
import sys

input = sys.stdin.buffer.readline

n = int(input())
A = list(map(int, input().split()))
infi = 10 ** 20
SA = list(accumulate([0] + A))

dp = [[infi] * (n + 1) for _ in range(n + 1)]
# dp[i]左からi個決めた時の最小値とする。
if n >= 3:
    for i in range(n):
        dp[i][i] = 0
        dp[i][i + 1] = 0
        if i <= n - 2:
            dp[i][i + 2] = A[i] + A[i + 1]
    for d in range(n + 1):
        for i in range(n):
            j = i + d
            if j > n:
                continue
            if d >= 2:
                for m in range(i + 1, j + 1):
                    dp[i][j] = min(dp[i][j], dp[i][m] + dp[m][j] + SA[j] - SA[i])
    print(dp[0][n])
else:
    print(sum(A))


Fixed submission:
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
infi = 10 ** 20
SA = list(accumulate([0] + A))

dp = [[infi] * (n + 1) for _ in range(n + 1)]
# dp[i]左からi個決めた時の最小値とする。
if n >= 3:
    for i in range(n):
        dp[i][i] = 0
        dp[i][i + 1] = 0
        if i <= n - 2:
            dp[i][i + 2] = A[i] + A[i + 1]
    for d in range(n + 1):
        for i in range(n):
            j = i + d
            if j > n:
                continue
            if d >= 2:
                for m in range(i + 1, j + 1):
                    dp[i][j] = min(dp[i][j], dp[i][m] + dp[m][j] + SA[j] - SA[i])
    print(dp[0][n])
else:
    print(sum(A))

Buggy python submission (verdict: Runtime Error):
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
infi = 10 ** 20
SA = list(accumulate([0] + A))

dp = [[infi] * (n + 1) for _ in range(n + 1)]
# dp[i]左からi個決めた時の最小値とする。
if n >= 3:
    for i in range(n):
        dp[i][i] = 0
        dp[i][i + 1] = 0
        if i <= n - 2:
            dp[i][i + 2] = A[i] + A[i + 1]
    for d in range(n + 1):
        for i in range(n):
            j = i + d
            if j > n:
                continue
            if d >= 2:
                for m in range(i + 1, j + 1):
                    dp[i][j] = min(dp[i][j], dp[i][m] + dp[m][j] + SA[j] - SA[i])
    print(dp[0][n])
else:


Fixed submission:
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
infi = 10 ** 20
SA = list(accumulate([0] + A))

dp = [[infi] * (n + 1) for _ in range(n + 1)]
# dp[i]左からi個決めた時の最小値とする。
if n >= 3:
    for i in range(n):
        dp[i][i] = 0
        dp[i][i + 1] = 0
        if i <= n - 2:
            dp[i][i + 2] = A[i] + A[i + 1]
    for d in range(n + 1):
        for i in range(n):
            j = i + d
            if j > n:
                continue
            if d >= 2:
                for m in range(i + 1, j + 1):
                    dp[i][j] = min(dp[i][j], dp[i][m] + dp[m][j] + SA[j] - SA[i])
    print(dp[0][n])
else:
    print(sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.buffer.readline
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (pow(2, n))
dp[0] = 1
# dp[i][j] 男i人に対して女の集合Sが合致
for s in range(pow(2, n)):
    otoko = bin(s).count("1")
    i = otoko
    for j in range(n):
        if (s >> j) & 1 == 0:
            if A[i][j] == 1:
                ns = s | 1 << j
                dp[ns] += dp[s]
                dp[ns] %= mod
print(dp[pow(2, n) - 1])


Fixed submission:
import sys

input = sys.stdin.buffer.readline
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (pow(2, n))
dp[0] = 1
# dp[i][j] 男i人に対して女の集合Sが合致
bitcnt = [0] * (pow(2, n) + 1)
for s in range(pow(2, n)):
    # otoko = bin(s).count("1")
    bitcnt[s] = bitcnt[s // 2] + s % 2
    i = bitcnt[s]
    for j in range(n):
        if (s >> j) & 1 == 0:
            if A[i][j] == 1:
                ns = s | 1 << j
                dp[ns] += dp[s]
                dp[ns] %= mod
print(dp[pow(2, n) - 1])

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (2 ** n)
dp[0] = 1
# dp[i][j] 男i人に対して女の集合Sが合致
for s in range(2 ** n):
    otoko = bin(s).count("1")
    i = otoko
    for j in range(n):
        if (s >> j) & 1 == 0:
            if A[i][j] == 1:
                ns = s | 1 << j
                dp[ns] += dp[s]
                dp[ns] %= mod
print(dp[2 ** n - 1])


Fixed submission:
import sys

input = sys.stdin.buffer.readline
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (pow(2, n))
dp[0] = 1
# dp[i][j] 男i人に対して女の集合Sが合致
bitcnt = [0] * (pow(2, n) + 1)
for s in range(pow(2, n)):
    # otoko = bin(s).count("1")
    bitcnt[s] = bitcnt[s // 2] + s % 2
    i = bitcnt[s]
    for j in range(n):
        if (s >> j) & 1 == 0:
            if A[i][j] == 1:
                ns = s | 1 << j
                dp[ns] += dp[s]
                dp[ns] %= mod
print(dp[pow(2, n) - 1])
Buggy python submission (verdict: Time Limit Exceeded):
n, kk = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

# nxnの行列積


def matrix_product(A, B):
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            for j in range(n):
                res[i][j] += A[i][k] * B[k][j]
                res[i][j] %= mod
    return res


def matrix_exponents(A, t):
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        res[i][i] = 1

    while t:
        if t & 1 == 1:
            res = matrix_product(res, A)
        A = matrix_product(A, A)
        t //= 2
    return res


temp = matrix_exponents(AA, kk)


ans = 0
for i in range(n):
    for j in range(n):
        ans += temp[i][j]
        ans %= mod
print(ans)


Fixed submission:
n, kk = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

# nxnの行列積


def matrix_product(A, B):
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            for j in range(n):
                res[i][j] += A[i][k] * B[k][j]
                res[i][j] %= mod
    return res


def matrix_exponents(A, t):
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        res[i][i] = 1

    while t:
        if t & 1 == 1:
            res = matrix_product(res, A)
        A = matrix_product(A, A)
        t //= 2
    return res


temp = matrix_exponents(AA, kk)


ans = 0
for i in range(n):
    for j in range(n):
        ans += temp[i][j]
        ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
dict={25:'Christmas',24:'Christmas Eve',23:'Christmas Eve Eve',22:'Christmas Eve Eve Eve'}
print(dict[input()])

Fixed submission:
dict={25:'Christmas',24:'Christmas Eve',23:'Christmas Eve Eve',22:'Christmas Eve Eve Eve'}
print(dict[int(input())])

Buggy python submission (verdict: Runtime Error):
dict={25:'Christmas',24:'Christmas Eve',23:'Christmas Eve Eve',22;'Christmas Eve Eve Eve'}
print(dict[input()])

Fixed submission:
dict={25:'Christmas',24:'Christmas Eve',23:'Christmas Eve Eve',22:'Christmas Eve Eve Eve'}
print(dict[int(input())])
Buggy python submission (verdict: Runtime Error):
n,x=map(int,input().split())
L=['']*51
L[0]='P'
for i in range(n+1):
    L[i+1]='B'+L[i]+'P'+L[i]+'B'
print(L[n][0:x].count('P'))

Fixed submission:
n,x=map(int,input().split())
len_l=[0]*(n+1)
len_l[0]=1
num_p=[0]*(n+1)
num_p[0]=1
for i in range(n):
    len_l[i+1]=3+2*len_l[i]
    num_p[i+1]=2*num_p[i]+1
def calc(a,b):
    if a==0:
        return 1
    if b<=0:
        return 0
    else:
        nagasa=len_l[a]
        if b==1:
            return 0
        elif b<=len_l[a-1]+1:
            return calc(a-1,b-1)
        elif b==len_l[a-1]+2:
            return num_p[a-1]+1
        elif b<=2*len_l[a-1]+2:
            return num_p[a-1]+1+calc(a-1, b-(len_l[a-1]+2))
        elif b==2*len_l[a-1]+3:
            return 2*num_p[a-1]+1
        else:
            print('okasi')
            return None
print(calc(n,x))
Buggy python submission (verdict: Runtime Error):
n = int(input())
XYH = [list(map(int, input().split())) for _ in range(n)]

takasa = [[-1] * (101) for _ in range(101)]
for i in range(n):
    x, y, h = XYH[i]
    if h == 0:
        continue
    for j in range(101):
        for k in range(101):
            if takasa[j][k] == -1:
                takasa[j][k] = abs(x - j) + abs(y - k) + h
            else:
                if takasa[j][k] == abs(x - j) + abs(y - k) + h:
                else:
                    takasa[j][k] = -2

for i in range(101):
    for j in range(101):
        if takasa[i][j] > 0:
            print(i, j, takasa[i][j])
            exit()


Fixed submission:
n = int(input())
XYH = [list(map(int, input().split())) for _ in range(n)]

for i in range(101):
    for j in range(101):
        temp = -1
        for x, y, h in XYH:
            if h == 0:
                continue
            temp = h + abs(x - i) + abs(y - j)
            break
        flag = 0
        for x, y, h in XYH:
            kouho = temp - (abs(x - i) + abs(y - j)) - h
            if kouho == 0:
                continue
            elif h == 0 and kouho < 0:
                continue
            else:
                flag = 1
                break
        if not flag:
            print(i, j, temp)
            exit()

Buggy python submission (verdict: Runtime Error):
import sys
n=int(input())
L=[]
for _ in range(n):
    x,y,h=map(int,input().split())
    L.append((x,y,h))
a,b,c=L[0]
mae=a+b+c
for i in range(101):
    for j in range(101):
        takasa=abs(a-i)+(b-j)+c
        flag=1
        for p,q,r in L:
            if r==100:
                ans=(p,q,r)
            if abs(p-i)+abs(q-j)+r == takasa:
                continue
            else:
                flag=0
        if flag:
            ans=(i,j,takasa)
print(*ans, sep=' ')

Fixed submission:
n = int(input())
XYH = [list(map(int, input().split())) for _ in range(n)]

for i in range(101):
    for j in range(101):
        temp = -1
        for x, y, h in XYH:
            if h == 0:
                continue
            temp = h + abs(x - i) + abs(y - j)
            break
        flag = 0
        for x, y, h in XYH:
            kouho = temp - (abs(x - i) + abs(y - j)) - h
            if kouho == 0:
                continue
            elif h == 0 and kouho < 0:
                continue
            else:
                flag = 1
                break
        if not flag:
            print(i, j, temp)
            exit()
Buggy python submission (verdict: Runtime Error):
from collections import Counter
n=int(input())
A=list(map(int,input().split()))
A1=A[0:n-1:2]
A2=A[1:n:2]
L=Counter(A)
L1=Counter(A1)
L2=Counter(A2)
comon=L.most_common()
comon1=L1.most_common()
comon2=L2.most_common()
hanbun=n//2
if len(comon)==1:
    print(hanbun)
else:
    cnt=0
    saidai11=comon1[0][1]
    saidai21=comon2[0][1]
    if saidai11>=saidai21:
        cnt+=hanbun-saidai11
        if saidai11==saidai21:
            cnt+=hanbun-comon2[1][1]
        else:
            cnt+=hanbun-saidai21
    else:
        cnt+=hanbun-saidai11
        if saidai11==saidai21:
            cnt+=hanbun-comon1[1][1]
        else:
            cnt+=hanbun-saidai11
    print(cnt)
    

Fixed submission:
from collections import Counter

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

kisu = A[0::2]
gusu = A[1::2]

CK = Counter(kisu)
CG = Counter(gusu)
CKM = CK.most_common(2)
CGM = CG.most_common(2)

if len(CKM) == 1 and len(CGM) == 1:
    if CKM[0][0] == CGM[0][0]:
        ans = n // 2
    else:
        ans = 0
elif len(CKM) == 1:
    if CKM[0][0] == CGM[0][0]:
        ans = n // 2 - CGM[1][1]
    else:
        ans = n // 2 - CGM[0][1]
elif len(CGM) == 1:
    if CKM[0][0] == CGM[0][0]:
        ans = n // 2 - CKM[1][1]
    else:
        ans = n // 2 - CKM[0][1]
else:
    if CKM[0][0] == CGM[0][0]:
        ans1 = n // 2 - CKM[1][1] + n // 2 - CGM[0][1]
        ans2 = n // 2 - CGM[1][1] + n // 2 - CKM[0][1]
        ans = min(ans1, ans2)
    else:
        ans = n - (CKM[0][1] + CGM[0][1])

print(ans)
Buggy python submission (verdict: Runtime Error):
n,m,x,y=map(int,input().split())
X=list(map(int,input().split()))
Y=list(map(int,input().split()))
max_X=max(X)
min_Y=min(Y)
print('No War' if max_x<min_Y else 'War')

Fixed submission:
n,m,x,y=map(int,input().split())
X=list(map(int,input().split()))
Y=list(map(int,input().split()))
max_X=max(X)
min_Y=min(Y)
print('No War' if max_X<min_Y and max_X<y and x<min_Y else 'War')
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
n,m=map(int,input().split())
mod=10**9+7
kaidan=[1]*(2*10**5+1)
gyaku=[1]*(2*10**5+1)

for i in range(1, 2*10**5):
    kaidan[i]=i*kaidan[i-1] % mod
    gyaku[i]=pow(kaidan[i],mod-2,mod)
def comb(a,b):
    if a>0 and b>0 and a-b>0:
        return (kaidan[a] * gyaku[b]*gyaku[a-b])%mod
    elif a==0 or b==0 or a-b==0:
        return 1
    else:
        return 0

soin=defaultdict(int)
while m>=2:
    for i in range(2,int(n**.5)+5):
        while m%i==0 and m!=0:
            m//=i
            soin[i]+=1
            if m==1:
                break
                
L=list(soin.values())
ans=1
for l in L:
    ans*=comb(l+n-1,l)
    ans%=mod
print(ans)

Fixed submission:
from collections import defaultdict
n,m=map(int,input().split())
mod=10**9+7
kaidan=[1]*(2*10**5+1)
gyaku=[1]*(2*10**5+1)

for i in range(1, 2*10**5):
    kaidan[i]=i*kaidan[i-1] % mod
    gyaku[i]=pow(kaidan[i],mod-2,mod)
def comb(a,b):
    if a>0 and b>0 and a-b>0:
        return (kaidan[a] * gyaku[b]*gyaku[a-b])%mod
    elif a==0 or b==0 or a-b==0:
        return 1
    else:
        return 0
def fctr1(n): 
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append([i,c])
            c=0
    if n!=1:
        f.append([n,1])
    return f
# soin=defaultdict(int)
# while m>=2:
#     for i in range(2,int(n**.5)+5):
#         while m%i==0 and m!=0:
#             m//=i
#             soin[i]+=1
#             if m==1:
#                 break
     
L=list(fctr1(m))
ans=1
for a,l in L:
    ans*=comb(l+n-1,l)
    ans%=mod
print(ans)
Buggy python submission (verdict: Runtime Error):
s=input()
k=int(input())
for i in range(len(s)):
    if s[i]!='1':
        place=i+1
        ans=s[i]
        break
print(ans if place<=k else 1)

Fixed submission:
s=input()
k=int(input())
place=101
ans=s[0]
for i in range(len(s)):
    if s[i]!='1':
        place=i+1
        ans=s[i]
        break
print(ans if place<=k else 1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
bridge=[0]*(n)
AB=[list(map(int,input().split())) for i in range(m)]
AB.sort(key=lambda x:x[1])
cnt=0
for i in range(m):
    p,q=AB[i]
    p-=1
    q-=1
    flag=0
    for j in range(p,q):
        if bridge[j]==1:
            flag=1
            break
    if flag:
        continue
    else:
        bridge[q-1]=1
        cnt+=1
print(cnt)

Fixed submission:
n, m = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
AB.sort(key=lambda x: [x[1]])
migi = 0
cnt = 0
for i in range(m):
    a, b = AB[i]
    if migi <= a:
        cnt += 1
        migi = b

print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
bridge=[0]*(n)
AB=[list(map(int,input().split())) for i in range(m)]
AB.sort(key=lambda x:x[1])
cnt=0
for i in range(m):
    p,q=AB[i]
    p-=1
    q-=1
    flag=0
    for j in range(p,q):
        if bridge[j]==1:
            flag=1
            break
    if flag:
        continue
    else:
        bridge[q-1]=1
        cnt+=1
print(cnt)

Fixed submission:
n, m = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
AB.sort(key=lambda x: [x[1]])
migi = 0
cnt = 0
for i in range(m):
    a, b = AB[i]
    if migi <= a:
        cnt += 1
        migi = b

print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
bridge=[0]*(n)
AB=[list(map(int,input().split())) for i in range(m)]
AB.sort(key=lambda x:x[1])
cnt=0
for i in range(m):
    p,q=AB[i]
    p-=1
    q-=1
    flag=0
    for j in range(p,q):
        if bridge[j]==1:
            flag=1
    if flag:
        continue
    else:
        bridge[q-1]=1
print(sum(bridge))

Fixed submission:
n, m = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
AB.sort(key=lambda x: [x[1]])
migi = 0
cnt = 0
for i in range(m):
    a, b = AB[i]
    if migi <= a:
        cnt += 1
        migi = b

print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
bridge=[0]*(n)
AB=[list(map(int,input().split())) for i in range(m)]
AB.sort(key=lambda x:x[1])
cnt=0
for i in range(m):
    p,q=AB[i]
    p-=1
    q-=1
    flag=0
    for j in range(p,q):
        if bridge[j]==1:
            flag=1
    if flag:
        continue
    else:
        bridge[q-1]=1
print(sum(bridge))

Fixed submission:
n, m = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
AB.sort(key=lambda x: [x[1]])
migi = 0
cnt = 0
for i in range(m):
    a, b = AB[i]
    if migi <= a:
        cnt += 1
        migi = b

print(cnt)
Buggy python submission (verdict: Runtime Error):
n=int(input())
A=list(map(int,input().split()))
print(abs((max(A)-min(A))

Fixed submission:
n=int(input())
A=list(map(int,input().split()))
print(abs(max(A)-min(A)))
Buggy python submission (verdict: Runtime Error):
A=[1]
for i in range(1,33):
  for j in range(1, 11):
    if i**j<X:
      A.append(i**j)
print(A[-1])

Fixed submission:
A=[1]
X=int(input())
for i in range(1,33):
  for j in range(2, 11):
    if i**j<X+1:
      A.append(i**j)
print(max(A))
Buggy python submission (verdict: Runtime Error):
s = input()
k = int(input())
n = len(list(s))
kouho = set()
for i in range(n):
    for d in range(1, k + 1):
        if i + d < n:
            kouho.add(s[i : i + d])
ans = list(kouho)
ans.sort()
print(ans[k - 1])


Fixed submission:
s = input()
k = int(input())
n = len(list(s))
kouho = set()
for i in range(n):
    for d in range(1, k + 1):
        if i + d <= n:
            kouho.add(s[i : i + d])
ans = list(kouho)
ans.sort()
# print(ans)
print(ans[k - 1])
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())

if m>=2 and n>=2:
    print((n-2)*(m-2))
elif m==1 and n>=2:
    print(n-2)
elif n==1 and m>=2:
    print(m-2)
else:
    prnit(1)

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

if m>=2 and n>=2:
    print((n-2)*(m-2))
elif m==1 and n>=2:
    print(n-2)
elif n==1 and m>=2:
    print(m-2)
else:
    print(1)