Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, K = map(int,input().split())
    moves = []
     
    mod = 998244353
     
    for _ in range(K):
        L, R = map(int,input().split())
        # for d in range(L, R+1):
        #     moves.append(d)
        moves.append((L, R))
    # moves.sort()
     
    dp = [0] * (N + 1)
    dp[1] = 1
    # for dis in moves:
    #     dp[dis] = 1
    # print(moves)
     
    for n in range(1, N+1):
        for L, R in moves:
            if n - L <= 0 :
                continue
            for dis in range(L, R+1):
                if n - dis >= 1:
                    dp[n] += dp[n - dis] % mod
                else:
                    break
     
    # print(dp)
    print(dp[N] % mod)

if __name__ == "__main__":
    main()


Fixed submission:
n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
mod = 998244353
N, K = map(int,input().split())

v = []
for _ in range(K):
    L, R = map(int,input().split())
    # for d in range(L, R+1):
    #     moves.append(d)
    v.append((L, R))
v.sort()

dp = [0] * N        # マスi-1に到達するまでの操作列の個数
sdp = [0] * (N + 1) # dp[i]までの累積和 
dp[0] = 1
sdp[1] = 1

for n in range(1, N):
    for p in v:
        left = max(0, n - p[1])
        right = max(0, n - p[0]+1)
        dp[n] += sdp[right] - sdp[left]
    sdp[n+1] = sdp[n] + dp[n]

print(dp[-1] % mod)

Fixed submission:
n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
mod = 998244353
N, K = map(int,input().split())

v = []
for _ in range(K):
    L, R = map(int,input().split())
    # for d in range(L, R+1):
    #     moves.append(d)
    v.append((L, R))

dp = [0] * N        # マスi-1に到達するまでの操作列の個数
sdp = [0] * (N + 1) # dp[i]までの累積和 
dp[0] = 1
sdp[1] = 1

for n in range(1, N):
    for p in v:
        left = max(0, n - p[1])
        right = max(0, n - p[0]+1)
        dp[n] += sdp[right] - sdp[left]
    sdp[n+1] = sdp[n] + dp[n]

print(dp[-1] % mod)



Fixed submission:
n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):

def main():
    mod = 998244353
    N, K = map(int,input().split())
    v = []
    
    for _ in range(K):
        L, R = map(int,input().split())
        # for d in range(L, R+1):
        #     moves.append(d)
        v.append((L, R))
    
    dp = [0] * N        # マスi-1に到達するまでの操作列の個数
    sdp = [0] * (N + 1) # dp[i]までの累積和 
    dp[0] = 1
    sdp[1] = 1

    for n in range(1, N):
        for p in v:
            left = max(0, n - p[1])
            right = max(0, n - p[0]+1)
            dp[n] += sdp[right] - sdp[left]
        sdp[n+1] = sdp[n] + dp[n]

    print(dp[-1] % mod)

if __name__ == "__main__":
    main()



Fixed submission:
n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):

def main():
    
    N, K = map(int,input().split())
    moves = []

    mod = 998244353

    for _ in range(K):
        L, R = map(int,input().split())
        # for d in range(L, R+1):
        #     moves.append(d)
        moves.append((L, R))
    moves.sort()

    dp = [0] * (N + 1)
    dp[1] = 1
    # for dis in moves:
    #     dp[dis] = 1
    # print(moves)

    for n in range(1, N+1):
        for L, R in moves:
            if n - L <= 0 :
                break
            for dis in range(L, R+1):
                if n - dis >= 1:
                    dp[n] += dp[n - dis]
                else:
                    break

    # print(dp)
    print(dp[N] % mod)


if __name__ == "__main__":
    main()


Fixed submission:
n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
moves = []

mod = 998244353

for _ in range(K):
    L, R = map(int,input().split())
    # for d in range(L, R+1):
    #     moves.append(d)
    moves.append((L, R))
moves.sort()

dp = [0] * (N + 1)
dp[1] = 1
# for dis in moves:
#     dp[dis] = 1
# print(moves)

for n in range(1, N+1):
    for L, R in moves:
        if n - L <= 0 :
            break
        for dis in range(L, R+1):
            if n - dis >= 1:
                dp[n] += dp[n - dis]
            else:
                break

# print(dp)
print(dp[N] % mod)


Fixed submission:
n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
moves = []

mod = 998244353

for _ in range(K):
    L, R = map(int,input().split())
    # for d in range(L, R+1):
    #     moves.append(d)
    moves.append((L, R))
# moves.sort()

dp = [0] * (N + 1)
dp[1] = 1
# for dis in moves:
#     dp[dis] = 1
# print(moves)

for n in range(1, N+1):
    for L, R in moves:
        if n - L <= 0 :
            continue
        for dis in range(L, R+1):
            if n - dis >= 1:
                dp[n] += dp[n - dis]
            else:
                break

# print(dp)
print(dp[N] % mod)


Fixed submission:
n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
moves = []

mod = 998244353

for _ in range(K):
    L, R = map(int,input().split())
    for d in range(L, R+1):
        moves.append(d)
    # moves.add((L, R))
moves.sort()

dp = [0] * (N + 1)
dp[1] = 1
# for dis in moves:
#     dp[dis] = 1
# print(moves)

for n in range(1, N+1):
    for dis in moves:
        if n - dis >= 1:
            dp[n] += dp[n - dis]
        else:
            break

# print(dp)
print(dp[N] % mod)


Fixed submission:
n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
moves = []

mod = 998244353

for _ in range(K):
    L, R = map(int,input().split())
    for d in range(L, R+1):
        moves.append(d)
    # moves.add((L, R))
moves.sort()

dp = [0] * (N + 1)
dp[1] = 1
# for dis in moves:
#     dp[dis] = 1
# print(moves)

for n in range(1, N+1):
    for dis in moves:
        if n - dis >= 1:
            dp[n] += dp[n - dis]
        else:
            break

# print(dp)
print(dp[N] % mod)


Fixed submission:
n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
moves = set()

mod = 998244353

for _ in range(K):
    L, R = map(int,input().split())
    for d in range(L, R+1):
        moves.add(d)
    # moves.add((L, R))


dp = [0] * (N + 1)
dp[1] = 1
# for dis in moves:
#     dp[dis] = 1

for n in range(1, N+1):
    for dis in moves:
        if n - dis >= 1:
            dp[n] += dp[n - dis]

# print(dp)
print(dp[N] % mod)


Fixed submission:
n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
moves = set()

mod = 998244353

for _ in range(K):
    L, R = map(int,input().split())
    for d in range(L, R+1):
        moves.add(d)

dp = [0] * (N + 1)
dp[1] = 1
# for dis in moves:
#     dp[dis] = 1

for n in range(1, N+1):
    for dis in moves:
        if n - dis >= 1:
            # print(n, n - dis)
            dp[n] += dp[n - dis]

# print(dp)
print(dp[N] % mod)


Fixed submission:
n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])