Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
import numpy as np

# import os
# path = os.getcwd()
# path = os.path.join(path,"input.txt")
# sys.stdin = open(path)

input = sys.stdin.readline
N,W  = map(int,input().split())
dp = np.zeros((N+1,W+1))
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

for row in range(N):
    dp[row+1,:w[row]] = dp[row,:w[row]]
    for col in range(w[row],W+1):
        dp[row+1,col] = max(v[row]+dp[row,col-w[row]],dp[row,col])

ans = int(max(dp[N]))
print(ans)

### FIXED CODE ###

import sys
import numpy as np


input = sys.stdin.readline
N,W  = map(int,input().split())
dp = np.zeros((N+1,W+1),dtype=int)
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

for row in range(N):
    dp[row+1,:w[row]] = dp[row,:w[row]]
    dp[row+1,w[row]:] = np.maximum(dp[row,w[row]:],v[row]+dp[row,:-w[row]])
print(dp[N,-1])
### BUGGY CODE ###

n = int(input())
nums = [int(input()) for _ in range(n)]
for i in range(n):
  print(max(nums[:i]+nums[i+1:]))

### FIXED CODE ###

n = int(input())
num = [int(input()) for _ in range(n)]
m = max(num)
sec = sorted(num)[-2]
for x in num:
    if x != m:
        print(m)
    else:
        print(sec)
### BUGGY CODE ###

string=input()
length=len(string)
mod=[1]+[0]*2018
s=0
for i in range(length):
  s=(s+int(string[-1-i])*pow(10,i))%2019
  mod[s]+=1
print(sum([i*(i-1)//2 for i in mod]))


### FIXED CODE ###

string=input()
length=len(string)
mod=[1]+[0]*2018
s=0
for i in range(length):
  s=(s+int(string[-1-i])*pow(10,i,2019))%2019
  mod[s]+=1
print(sum([i*(i-1)//2 for i in mod]))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, S: str):
    
    ans = 0
    for i in range(N):
        for j in range(i+1, min(i+1+N//2, N)):
            st = S[i:j]
            # print(st)
            if(S.count(st) > 1):
                ans = max(ans, len(st))

    print(ans)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, S: str):
    
    ans = 0
    x = []
    for i in range(N):
        x.append(S[i])
        xj = ''.join(x)
        if(S[i+1:].count(xj)):
            ans = max(ans, len(xj))
        else:
            x.pop(0)

    print(ans)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    d, g = MI()
    data = np.array([LI() for _ in range(d)], np.int64)
    p = data[:, 0]
    c = data[:, 1]

    problems = np.zeros(2 ** d, np.int64)
    points = np.zeros(2 ** d, np.int64)
    for i in range(d):
        problems[1 << i : 1 << (i + 1)] = problems[: 1 << i] + p[i]
        points[1 << i : 1 << (i + 1)] = points[: 1 << i] + c[i] + 100 * (i + 1) * p[i]

    for i in range(2 ** d):
        while points[i] < g:
            for j in reversed(range(d)):
                if (i >> j) & 1:
                    continue
                for _ in range(p[j]):
                    if points[i] >= g:
                        break
                    points[i] += 100 * (j + 1)
                    problems[i] += 1

    print(problems.min())


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


inf = float("inf")


def main():
    d, g = MI()
    pc = [LI() for _ in range(d)]

    ans = inf
    for bit in range(2 << d):
        c = 0
        score = 0
        for i in range(d):
            if bit & (1 << i):
                c += pc[i][0]
                score += pc[i][0] * 100 * (i + 1) + pc[i][1]

        if score >= g:
            ans = min(ans, c)
        else:
            for i in reversed(range(d)):
                if bit & (1 << i):
                    continue
                res = math.ceil((g - score) / (100 * (i + 1)))
                if res < pc[i][0]:
                    ans = min(ans, c + res)
                break

    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
for lz in range(Q):
  l1,l2=map(int,input().split())
  s1=S[l1-1:l2]
  z=0
  flg=0
  for k in s1:
    if k == 'A':
      flg=1
      continue
    elif k == 'C' and flg == 1:
      z+=1
    flg=0
  print(z)

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
k = [0] * (N+1)

for i in range(1,N):
  v = 1 if S[i-1]+S[i] == 'AC' else 0
  k[i] = k[i-1] + v
k[-1]=k[-2]
for _ in range(Q):
  f,l = map(int,input().split())
  print(k[l-1] - k[f-1])
### BUGGY CODE ###

N, K = map(int, input().split())

if N == K:
    print(0)

elif N<K and N<=K-N:
    print(N)

elif N<K and N>K-N:
    print(K-N)

elif N>K:
    while N>0:
        N = N - K
    if -N<N+K:
        print(-N)
    else:
        print(N + K)


### FIXED CODE ###

N, K = map(int, input().split())

if N%K == 0:
    print(0)

elif N<K and N<=K-N:
    print(N)

elif N<K and N>K-N:
    print(K-N)

elif N>K:
    if K-(N%K)>N%K:
        print(N%K)
    else:
        print(K-(N%K))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
s=[]
for i in range(h):
	s.append(input().rstrip())
num=[[0]*w for _ in range(h)]
for i in range(h):
	p=0
	for j in range(w):
		if s[i][j]==".":
			p+=1
			num[i][j]+=p
		else:
			p=0
for i in range(h):
	p=0
	for j in range(w-1,-1,-1):
		if s[i][j]==".":
			p+=1
			num[i][j]+=p
		else:
			p=0
for i in range(w):
	p=0
	for j in range(h):
		if s[j][i]==".":
			p+=1
			num[j][i]+=p
		else:
			p=0
for i in range(w):
	p=0
	for j in range(h-1,-1,-1):
		if s[j][i]==".":
			p+=1
			num[j][i]+=p
		else:
			p=0
ans=0
for i in range(h):
	ans=max(ans,max(num[i])-3)
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
s=[]
for i in range(h):
	s.append(input().rstrip())
num=[[0]*w for _ in range(h)]
for i in range(h):
	p=0
	for j in range(w):
		if s[i][j]==".":
			p+=1
			num[i][j]+=p
		else:
			p=0
for i in range(h):
	p=0
	for j in range(w-1,-1,-1):
		if s[i][j]==".":
			p+=1
			num[i][j]+=p
		else:
			p=0
for i in range(w):
	p=0
	for j in range(h):
		if s[j][i]==".":
			p+=1
			num[j][i]+=p
		else:
			p=0
for i in range(w):
	p=0
	for j in range(h-1,-1,-1):
		if s[j][i]==".":
			p+=1
			num[j][i]+=p
		else:
			p=0
ans=0
for i in range(h):
	ans=max(ans,max(num[i])-3)
print(ans)
### BUGGY CODE ###

import sys
import numpy as np 
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False)
    if np.any(A - B > 0):
        return -1

    will_subtract = []
    for v in range(n-1):
        for u in range(v+1, n):
            d = B[v, u]
            for w in range(v):
                if B[v, w] + B[w, u] == d:
                    will_subtract.append(d)
                    break
            else:
                for w in range(v+1, u):
                    if B[v, w] + B[w, u] == d:
                        will_subtract.append(d)
                        break
                else:
                    for w in range(u+1, n):
                        if B[v, w] + B[w, u] == d:
                            will_subtract.append(d)
                            break

    ans = np.sum(B) // 2 - sum(will_subtract)
    return int(ans)

if __name__ == '__main__':
    ans = main()
    print(ans)

### FIXED CODE ###

import sys
import numpy as np 
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.float64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False).astype(np.int64)
    if np.any(B < A):
        return -1
        
    np.fill_diagonal(A, np.inf)
    
    total_length = 0
    for v in range(n-1):
        for u in range(v+1, n):
            detours = A[v] + A[u]
            if np.all(detours > B[v, u]):
                total_length += B[v, u]

    return total_length

if __name__ == '__main__':
    ans = main()
    print(ans)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
p = list(map(int, input().split()))

max_e = 0

l = list(map(lambda x: (x + 1) / 2, p))

for i in range(N - K + 1):
    e = 0
    for j in range(K):
        e += l[i + j]
    if e > max_e:
        max_e = e

print(max_e)


### FIXED CODE ###

N, K = list(map(int, input().split()))
p = list(map(int, input().split()))

# cumulated value
c_p = [0] * N
c_p[0] = p[0]

for i in range(1, N):
    c_p[i] = c_p[i - 1] + p[i]

max_e = c_p[K - 1]

for i in range(K, N):
    e = c_p[i] - c_p[i - K]
    max_e = max(max_e, e)

print((max_e + K) / 2)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
m=1/k
ans=0
l=[]
for i in range(k):
  tmp=0
  for j in range(1,p[i]+1):
    tmp+=1/p[i]*j
  l.append(tmp)
ans=sum(l)
for i in range(k,n):
  tmp=0
  s=0
  for j in range(1,p[i]+1):
    tmp+=1/p[i]*j
  l.append(tmp)
  s=sum(l[i-k+1:i+1])
  if ans<s:
    ans=s
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
l=[0]*(n+1)
l[1]=(p[0]+1)/2
for i in range(2,n+1):
  l[i]=l[i-1]+(p[i-1]+1)/2
ans=0
for i in range(n-k+1):
  if ans<l[i+k]-l[i]:
    ans=l[i+k]-l[i]
print(ans)
### BUGGY CODE ###

import math
from functools import reduce
import itertools
import numpy as np


def gcd_list(numbers):
    return reduce(math.gcd, numbers)


K = int(input())

l = [i for i in range(1, K + 1)]

temp_sum = np.array([])
for j in itertools.product(l, repeat=3):
    temp_sum=np.append(temp_sum,gcd_list(list(j)))


print(int(np.sum(temp_sum)))

### FIXED CODE ###

import math
from functools import reduce
import itertools
import numpy as np

K = int(input())



ans = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        for k in range(j, K + 1):
            if i == j and j == k:
                dup_num = 1
            elif i == j or j == k:
                dup_num = 3
            else:
                dup_num = 6
            ans += math.gcd(math.gcd(i, j), k) * dup_num

print(ans)
### BUGGY CODE ###

# ContestName
# URL
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def check(i, j, q, count, H, W, A, rec):
    if i < 0 or i >= H:
        return count
    if j < 0 or j >= W:
        return count
    if A[i][j] == '#':
        return count
    A[i][j] = '#'
    count += 1
    q.append((i, j))
    return count

def main():
    H, W = i2nn()
    A = ii2ss(H)
    A = [list(s) for s in A]
    B = A
    HW = H * W
    q = []
    count = 0
    rec = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                q.append((i, j))
                count += 1
    while True:
        if count >= HW:
            print(rec)
            return
        rec += 1
        q2 = []
        for i, j in q:
            count = check(i-1, j, q2, count, H, W, B, rec)
            count = check(i+1, j, q2, count, H, W, B, rec)
            count = check(i, j-1, q2, count, H, W, B, rec)
            count = check(i, j+1, q2, count, H, W, B, rec)
        q = q2

main()


### FIXED CODE ###

# AtCoder Grand Contest 033
# https://atcoder.jp/contests/agc033
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

import datetime

def main():
    H, W = i2nn()
    HW = H * W
    A = ii2ss(H)
    A = [[0 if s == '#' else HW for s in line] for line in A]
    for i in range(H):
        for j in range(1, W):
            if A[i][j-1]+1 < A[i][j]:
                A[i][j] = A[i][j-1]+1
        for j in range(W-2, -1, -1):
            if A[i][j+1]+1 < A[i][j]:
                A[i][j] = A[i][j+1]+1
    for j in range(W):
        for i in range(1, H):
            if A[i-1][j]+1 < A[i][j]:
                A[i][j] = A[i-1][j]+1
        for i in range(H-2, -1, -1):
            if A[i+1][j]+1 < A[i][j]:
                A[i][j] = A[i+1][j]+1
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] > ans:
                ans = A[i][j]
    print(ans)

main()
### BUGGY CODE ###

# standard input
S = input()
Q = int(input())
Query = []
num_reverse = 0

for _ in range(Q):

    q = tuple(map(str, input().split()))

    if int(q[0]) == 1:
        num_reverse += 1

    else:
        if (num_reverse + int(q[1])) % 2 == 0:
            S = S + q[2]
        else:
            S = q[2] + S

if num_reverse % 2 == 1:
    # S = S[::-1]
    S = ''.join(reversed(S))

print(S)


### FIXED CODE ###

# standard input
S = input()
Q = int(input())
Query = []
num_reverse = 0

L = ''
R = ''

rev = False

for _ in range(Q):

    q = tuple(map(str, input().split()))

    if q[0] == '1':
        rev = (not rev)

    else:
        if (rev and q[1] == '1') or (not rev and q[1] == '2'):
            R = R + q[2]
        else:
            L = q[2] + L 

if rev:
    print( R[::-1] + S[::-1] + L[::-1])
else:
    print( L + S + R )
### BUGGY CODE ###

people=[0 for i in range(6)]
move=[0 for i in range(5)]
n=int(input())
people[0]=n
limit=[0 for i in range(5)]
for i in range(5):
  limit[i]=int(input())
time=0
while people[5]<n:
  for i in range(5):
    move[i]=(min(people[i],limit[i]))
    people[i]-=move[i]
  for i in range(5):
    people[i+1]+=move[i]
  time+=1
print(time)

### FIXED CODE ###

n=int(input())
limit=[]
for i in range(5):
  a=int(input())
  limit.append(a)
time=n//min(limit)
if n%min(limit)==0:
  time-=1
print(time+5)
### BUGGY CODE ###

#D - Dice in Line
#一つのサイコロふったときに出る目の期待値は(面の数+1)/2
#面の数から期待値に変換してからforぶん回して無理やり最大値を求める
n,k=list(map(int,input().split()))
dices = list(map(float,input().split()))
expected = []
answer = 0
sumOfValue = 0
#サイコロの目を期待値に変換
for eyes in dices:
    expected.append((eyes+1)/2)
#最大値を求める
for maxvalue in range(len(expected)-k+1):
    sumOfValue = sum(expected[maxvalue:maxvalue+k])
    if(answer < sumOfValue):
        answer = sumOfValue
print(answer)

### FIXED CODE ###

#D - Dice in Line
#一つのサイコロふったときに出る目の期待値は(面の数+1)/2
n,k=list(map(int,input().split()))
dices = list(map(float,input().split()))
expected = []
answer = 0
i = 0
j = 0
sumOfValue = 0
expected.append(i)
#サイコロの目を期待値に変換して累積和のリスト作る
for eyes in dices:
    i = (eyes+1)/2
    j = j + i
    expected.append(j)
#最大値を求める
for t in range(n-k+1):
    sumOfValue = expected[t+k] - expected[t]
    if(answer <= sumOfValue):
        answer = sumOfValue
print(answer)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
if a[0] > 0 or a.count(0) > 1:
  print(0)
  exit()
  
a = sorted(a)
dp = [0]*(n+1)
dp[0] = 1
count_list = [0]*n
count_list[0] = 1
for i in range(1, n):
  count_list[a[i]] += 1
  dp[a[i]] = dp[a[i]-1] * count_list[a[i]-1] ** count_list[a[i]] % 998244353
print(dp[a[n-1]])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if a[0] > 0 or a.count(0) > 1:
  print(0)
  exit()
  
a = sorted(a)
dp = [0]*(n+1)
dp[0] = 1
count_list = [0]*n
count_list[0] = 1
for i in range(1, n):
  count_list[a[i]] += 1
for i in range(1, a[n-1]+1):
  dp[i] = dp[i-1] * count_list[i-1] ** count_list[i] % 998244353
print(dp[a[n-1]])
### BUGGY CODE ###

n, k = map(int, input().split())
seq = [bool(int(c)) for c in input()]

ones = []
if seq[0] is False:
    ones.append(0)
zeros = []
state = True
cnt = 0
for i, c in enumerate(seq):
    if i == 0:
        state = c
        cnt = 1
        continue

    if c == state:
        cnt += 1
    else:
        if state:
            ones.append(cnt)
        else:
            zeros.append(cnt)
        cnt = 1
        state = c

if state is True:
    ones.append(cnt)
else:
    ones.append(0)
    zeros.append(cnt)

# print(ones)
# print(zeros)

if k > len(zeros):
    k = len(zeros)

scores = []
for i in range(len(zeros) - k + 1):
    scores.append(sum(ones[i:i+k+1]) + sum(zeros[i:i+k]))

print(max(scores))


### FIXED CODE ###

n, k = map(int, input().split())
seq = [bool(int(c)) for c in input()]

ones = []
if seq[0] is False:
    ones.append(0)
zeros = []
state = True
cnt = 0
for i, c in enumerate(seq):
    if i == 0:
        state = c
        cnt = 1
        continue

    if c == state:
        cnt += 1
    else:
        if state:
            ones.append(cnt)
        else:
            zeros.append(cnt)
        cnt = 1
        state = c

if state is True:
    ones.append(cnt)
else:
    ones.append(0)
    zeros.append(cnt)

# print(ones)
# print(zeros)

n_zeros = len(zeros)

k = min(k, n_zeros)

cum_ones = []
for i, num in enumerate(ones):
    if i == 0:
        cum_ones.append(num)
        continue
    cum_ones.append(num + cum_ones[-1])
cum_zeros = []
for i, num in enumerate(zeros):
    if i == 0:
        cum_zeros.append(num)
        continue
    cum_zeros.append(num + cum_zeros[-1])

max_score = 0
for i in range(n_zeros - k + 1):
    score = 0
    score += (cum_ones[i+k] - cum_ones[i-1]) if i > 0 else cum_ones[i+k]
    if k > 0:
        score += (cum_zeros[i+k-1] - cum_zeros[i-1]) if i > 0 else cum_zeros[i+k-1]
    if max_score < score:
        max_score = score

print(max_score)
### BUGGY CODE ###

from collections import Counter

H, W, M = map(int, input().split())
counterH = [0] * H
counterW = [0] * W
setHW = set({})
for _ in range(M):
    hi, wi = map(lambda x: int(x) - 1, input().split())
    setHW.add((hi, wi))
    counterH[hi] += 1
    counterW[wi] += 1


set_max_h, set_max_w = set(), set()
max_h, max_w = -1, -1

for h in range(H):
    if counterH[h] > max_h:
        max_h = counterH[h]
        set_max_h = set({h})
    elif counterH[h] == max_h:
        set_max_h.add(h)

for w in range(W):
    if counterW[w] > max_w:
        max_w = counterW[w]
        set_max_w = set({w})
    elif counterW[w] == max_w:
        set_max_w.add(w)
    
def count(h, w):
    bomb = 0 if (h, w) not in setHW else -1
    bomb += counterH[h]
    bomb += counterW[w]
    return bomb

m = -1
for h in set_max_h:
    for w in range(W):
        m = max(m, count(h, w))
for w in set_max_w:
    for h in range(H):
        m = max(m, count(h, w))

print(m)

### FIXED CODE ###

H, W, M = map(int,input().split())
Bomb = []
for _ in range(M):
    hi, wi = map(lambda x: int(x) - 1, input().split())
    Bomb.append((hi, wi))

counterH = [0] * H
counterW = [0] * W

for (hi, wi) in Bomb:
    counterH[hi] += 1
    counterW[wi] += 1

# 最大のところを選ぶ
max_h = max(counterH)
max_w = max(counterW)

count = 0
for (hi, wi) in Bomb:
    if counterH[hi] == max_h and counterW[wi] == max_w:
        count += 1

# 共通部分を確認 (-1)
ans = max_h + max_w
if count == counterH.count(max_h) * counterW.count(max_w):
    ans -= 1
print(ans)
### BUGGY CODE ###

a,b=map(int,input().split())
for i in range(1,10**7):
  if int(0.08*i)==a and int(0.1*i)==b:
    print(i)
    exit()
print(-1)

### FIXED CODE ###

a,b=map(int,input().split())
for i in range(1,10**8):
  if int(0.08*i)==a and int(0.1*i)==b:
    print(i)
    exit()
print(-1)
### BUGGY CODE ###


N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
MOD = 998244353

dp = [0] * (N + 1)
dp[1] = 1

for i in range(1, N):
    for l, r in X:
        for k in range(l, r + 1):
            if i + k > N:
                break
            dp[i + k] += dp[i]
            dp[i + k] %= MOD

print(dp[-1])


### FIXED CODE ###


N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
MOD = 998244353

dp = [0] * N
sdp = [0] * (N + 1)
dp[0] = 1
sdp[1] = 1

for i in range(1, N):
    for l, r in X:
        dp[i] += sdp[max(0, i - l + 1)] - sdp[max(0, i - r)]
        dp[i] %= MOD
    sdp[i + 1] = sdp[i] + dp[i]
    sdp[i + 1] %= MOD

print(dp[-1])
### BUGGY CODE ###

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N)]
    if S[-1] == '?':
        for j in range(10):
            dp[0][j] += 1
    else:
        dp[0][int(S[-1])] += 1
    for i in range(N-1):
        for k in range(13):
            if S[-(i+2)] != '?':
                dp[i+1][(k+int(S[-(i+2)])*(10**(i+1))%13)%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+2)])*(10**(i+1))%13)%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*(10**(i+1))%13)%13] += dp[i][k]
                    dp[i+1][(k+l*(10**(i+1))%13)%13] %= MOD
    print(dp[-1][5])





if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] += 1
    s=[1]
    for n in range(1,N):
        s.append((s[n-1]*10)%13)
    for i in range(N):
        for k in range(13):
            if S[-(i+1)] != '?':
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*s[i])%13] += dp[i][k]
                    dp[i+1][(k+l*s[i])%13] %= MOD
    print(dp[-1][5])

if __name__ == '__main__':
    main()
### BUGGY CODE ###

k,n  = map(int,input().split())
diff = lambda x:x[1]-x[0]
sum_list = lambda x:sum(x)
a = list(map(int,input().split()))
distance = a+[a[0]+k]
diffs = [diff(distance[i:i+2]) for i in range(len(distance)-1)]
diffs = diffs + [diffs[i] for i in range(0,n-2)]
sums = [sum_list(diffs[i:i+n-1]) for i in range(len(diffs)-(n-2))]
print(min(sums))


### FIXED CODE ###

k,n  = map(int,input().split())
diff = lambda x:x[1]-x[0]
a = list(map(int,input().split()))
distance = a+[a[0]+k]
diffs = [diff(distance[i:i+2]) for i in range(len(distance)-1)]
print(k - max(diffs))