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

s = [int(input()) for i in range(6)]
n = s[0]
#a,b,c,d,e = s[1],s[2],s[3],s[4],s[5]
dp = [n]+[0]*5
cnt = 0
while dp[-1] < n:
  for i in reversed(range(1,6)):
    if dp[i-1] <= s[i]:
      dp[i] += dp[i-1]
      dp[i-1] = 0
    else:
      dp[i] += s[i]
      dp[i-1] -= s[i]
  cnt += 1

print(cnt)

### FIXED CODE ###

import math
n = int(input())
s = [int(input()) for i in range(5)]
m = min(s)
ans = 4 + math.ceil(n/m)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
N=int(input())
MAXN=1005
MAXV=N*(N-1)//2

a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1

id=[[0 for j in range(MAXN)] for i in range(MAXN)]
v=0
for i in range(N-1):
  for j in range(i+1,N):
    id[i][j]=v
    v+=1

def toId(i,j):
  if i>j:
    i,j=j,i
  return id[i][j]

to=[[] for i in range(MAXV)]
for i in range(N):
  for j in range(N-1):
    a[i][j]=toId(i,a[i][j])
  for j in range(N-2):
    to[a[i][j+1]].append(a[i][j])
    
visited=[False for i in range(MAXV)]
calculated=[False for i in range(MAXV)]
dp=[0 for i in range(MAXV)]

def dfs(v):
  if visited[v]:
    if not calculated[v]:
      return -1
    return dp[v]
  visited[v]=True
  for u in to[v]:
    val=dfs(u)
    if val==-1:
      return -1
    if val+1>dp[v]:
      dp[v]=val+1
  calculated[v]=True
  return dp[v]
    
ans=0
for i in range(v):
  res=dfs(i)
  if res==-1:
    print(-1)
    break
  if ans<res:
    ans=res
else:
  print(ans+1)

### FIXED CODE ###

N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
q=[]

#seen=[[False for j in range(N)] for i in range(N)]

# 選手nが試合できるならqueに入れる
def check(i):
  if len(a[i])==0:
    return False
  j=a[i][-1]
  if a[j][-1]==i:
    q.append([i,j])
  
for i in range(N):
  check(i)
  
from collections import defaultdict

day=0
while q:
  day+=1
 # q=sorted(q)
  prevQ=q.copy()
  q=[]
  matched=defaultdict(list)
  for p in prevQ:
    i=p[0]
    j=p[1]
    if i>j:
      i,j=j,i
    if matched[i]:
      continue
    a[i].pop()
    a[j].pop()
    check(i)
    check(j)
    matched[i].append(j)
    
for i in range(N):
  if len(a[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import itertools
import numpy
def main():
    H, W, M = [int(j) for j in input().split()]
    Hx = [0]*H
    Wx = [0]*W
    dict = [[0] * W for i in range(H)]
    for i in range(M):
        h, w =  [int(j) for j in input().split()]
        dict[h-1][w-1]=1
        Hx[h-1] += 1
        Wx[w-1] += 1
    ans = max(Hx)+ max(Wx)
    maxIndex_Hx = [i for i, x in enumerate(Hx) if x == max(Hx)]
    maxIndex_Wx = [i for i, x in enumerate(Wx) if x == max(Wx)]

    ax = numpy.zeros((H,1))
    for i in maxIndex_Hx:
        ax[i][0] = 1
    ay = numpy.zeros((1,W))
    for i in maxIndex_Wx:
        ay[0][i] = 1
    az = numpy.dot(ax, ay)
    dot = numpy.multiply(numpy.array(dict),az)
    #print(dot)
    if numpy.sum(dot) != numpy.sum(az):
        print(ans)
    else:
        print(ans-1)
    '''
    if ans = H+W:
        print(H+W-1)
        return
    for j in list(itertools.product(maxIndex_Hx, maxIndex_Wx)):
        if dict[j[0]][j[1]] == 0:
            print(ans)
            return
    print(ans-1)
    '''
if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
W,H,M=[int(_) for _ in input().split()]
HW=[[int(_) for _ in input().split()]for i in range(M)]
yoko = [0]*W
tate = [0]*H
for hw in HW:
    yoko[hw[0]-1]+=1
    tate[hw[1]-1]+=1

my=max(yoko)
mt =max(tate)
ans = mt+my

cu=yoko.count(my)*tate.count(mt)
c = 0

for hw in HW:
    if yoko[hw[0]-1]==my and tate[hw[1]-1]==mt:
        c+=1
if c== cu:
    ans-=1
print(ans)
### BUGGY CODE ###

import numpy as np

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

ans = 0
for s in range(len(A)-1):
    ans += A[s]*sum(A[s+1:])

print(np.mod(ans,10**9+7))

### FIXED CODE ###

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

k = 1000000007

sm = sum(A)

ans = 0
for s in range(len(A)-1):
    #ans += A[s]*sum(A[s+1:])
    sm -= A[s]
    ans += A[s]*sm

if ans>1000000007:
    print(ans%k)
else:
    print(ans)
### BUGGY CODE ###

S = str(input())
S = [s for s in S]
Q = int(input())

flip = False

for q in range(0, Q):
    qi = list(input().split())

    if len(qi) == 1:
        flip = not flip
    else: # len(qi) == 3
        Fi, Ci = int(qi[1]), qi[2]
        
        if Fi == 1: # front 
            if not flip:
                S.insert(0, Ci)
            else: # flip == True
                S.append(Ci)
        else:
            if not flip:
                S.append(Ci)
            else:
                S.insert(0, Ci)

S = "".join(S)

print( S if not flip else S[::-1])


### FIXED CODE ###

S = str(input())
Q = int(input())

flip = False

head = ""
tail = ""

for q in range(Q):
    Ti = input()
    if Ti == '1':
        flip = not flip
    else:
        _, Fi, Ci = map(str, Ti.split())
        Fi = int(Fi)

        if (Fi^flip)&1:
            head += Ci
        else:
            tail += Ci

S = head[::-1] + S + tail
print( S if not flip else S[::-1])
### BUGGY CODE ###

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

bit = [0] * 60
mod = 10 ** 9 + 7
ans = 0
for i in range(60):
    c = 0
    for j in range(n):
        if a[j] & 1:
            c += 1
        a[j] //= 2
    ans = (ans + c * (n - c) * (2 ** i)) % mod

print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))

bit = [0] * 60
mod = 10 ** 9 + 7
ans = 0
for i in range(60):
    n1 = np.count_nonzero((a >> i) & 1)
    n0 = n - n1
    ans += (2 ** i) * n1 * n0 % mod
print(ans % mod)
### BUGGY CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n = II()
a = LI()

b = [0]*(n+1)
d = [0]*(n+1)
for i in set(a):
    c = a.count(i)
    b[i] += (c*(c-1)/2)
    d[i] += c
sumb = sum(b)
for i in a:
    print(int(sumb - (d[i]-1)))

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n = II()
a = LI()

b = [0]*(n+1)
count = 0
for i in range(n):
    b[a[i]] += 1
for i in range(n+1):
    count += b[i]*(b[i]-1)/2
for i in a:
    print(int(count-b[i]+1))
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
import sys
input = sys.stdin.readline

def dfs(v):
    visited[v] = True
    for i in range(len(AL[v][CHILDREN])):
        u = AL[v][CHILDREN][i]
        if visited[u]:
            AL[v][CHILDREN][i] = None
            continue
        AL[v][SIZE] += dfs(u)
    return AL[v][SIZE]

def anaaki(v):
    ret = pow(2, n - 1, p) - 1
    for ch in AL[v][CHILDREN]:
        if ch is None: continue
        ret -= pow(2, AL[ch][SIZE], p) - 1
        ret %= p
    ret -= pow(2, n - AL[v][SIZE], p) - 1
    ret %= p
    return ret

n = int(input())
SIZE = 0
CHILDREN = 1
AL = [[1, []] for _ in range(n)]
visited = [False] * n
p = 10 ** 9 + 7
for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    AL[a][CHILDREN].append(b)
    AL[b][CHILDREN].append(a)

dfs(0)
que = deque([0])
numer = 0
while que:
    next = que.popleft()
    numer += anaaki(next)
    numer %= p
    for ch in AL[next][CHILDREN]:
        if ch is not None:
            que.append(ch)

denom = pow(2, n, p)
print(numer * pow(denom, p - 2, p) % p)

### FIXED CODE ###

# classを使うのをやめてlistで実施する
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
import sys
input = sys.stdin.readline

def dfs(v):
    visited[v] = True
    for i in range(len(AL[v][CHILDREN])):
        u = AL[v][CHILDREN][i]
        if visited[u]:
            AL[v][CHILDREN][i] = None
            continue
        AL[v][SIZE] += dfs(u)
    return AL[v][SIZE]


def anaaki(v):
    ret = powp - 1
    for ch in AL[v][CHILDREN]:
        if ch is None: continue
        ret -= pow(2, AL[ch][SIZE], p) - 1
        ret %= p
    ret -= pow(2, n - AL[v][SIZE], p) - 1
    ret %= p
    return ret

n = int(input())
SIZE = 0
CHILDREN = 1
AL = [[1, []] for _ in range(n)]
visited = [False] * n
p = 10 ** 9 + 7
powp = pow(2, n - 1, p)

for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    AL[a][CHILDREN].append(b)
    AL[b][CHILDREN].append(a)

dfs(0)
numer = 0
for i in range(n):
    numer += anaaki(i)
    numer %= p

denom = pow(2, n, p)
print(numer * pow(denom, p - 2, p) % p)
### BUGGY CODE ###

N, X, M = map(int, input().split())
NN = N
li = []
isused = [False] * M
while isused[X] == False and N != 0:
    li.append(X)
    X = (X ** 2) % M
    N -= 1
    
if N == 0:
    print(sum(li))

elif N != 0 and X in li:
    l = len(li)
    s = li.index(X)
    T = l - s
    q = (NN - s) // T
    r = (NN - s) % T
    print(sum(li) + sum(li[i] for i in range(s, len(li))) * (q-1) + sum(li[i] for i in range(s, s + r)))

### FIXED CODE ###

N, X, M = map(int, input().split())
NN = N
li = []
isused = [False] * M
while isused[X] == False and N != 0:
    li.append(X)
    isused[X] = True
    X = (X ** 2) % M
    N -= 1
    
if N == 0:
    print(sum(li))

elif N != 0 and X in li:
    l = len(li)
    s = li.index(X)
    T = l - s
    q = (NN - s) // T
    r = (NN - s) % T
    print(sum(li) + sum(li[i] for i in range(s, len(li))) * (q-1) + sum(li[i] for i in range(s, s + r)))
### BUGGY CODE ###

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

w, v = [0]*N, [0]*N 
for _ in range(N):
    w[_], v[_] = map(int, input().split())

dp = [[0]*(W+1) for _ in range(N+1)]
    
def npsk_1(N, W):
    for i in range(N):
        for j in range(W+1):
            if j - w[i] >= 0:
                dp[i+1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
            else:
                dp[i+1][j] = dp[i][j]
    
    print(dp[N][W])

npsk_1(N, W)

### FIXED CODE ###

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

w, v = [0] * N, [0] * N

for i in range(N):
	w[i], v[i] = map(int, input().split())

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

for i in range(N):
	for j in range(W + 1):
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
		else:
		    dp[i + 1][j] = dp[i][j] 

print(dp[N][W])
### BUGGY CODE ###

import sys
input=sys.stdin.readline

n=int(input())
s=input()
dp=[[[False]*1000 for j in range(4)] for i in range(n+1)]

dp[0][0][0]=True

for i in range(n):
    for j in range(4):
        for k in range(1000):
            if dp[i][j][k]==False:continue
            dp[i+1][j][k]=True
            if j<=2:
                dp[i+1][j+1][k*10+int(s[i])]=True
cnt=0
for i in range(1000):
    if dp[n][3][i]==1:cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
s=list(map(int,list(input())))
ans=0
for i in range(10):
    try:
        ss=s[s.index(i)+1:]
        for j in range(10):
            try:
                sss=ss[ss.index(j)+1:]
                for k in range(10):
                    if k in sss:ans+=1
            except:pass
    except:pass

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

import sys
sys.setrecursionlimit(10**7)
M=10**9+7
N=10**5*2
fac=[0]*(N+1)
fac[0]=b=1
for i in range(1,N+1):fac[i]=b=b*i%M
inv=[0]*(N+1)
inv[N]=b=pow(fac[N],M-2,M)
for i in range(N,0,-1):inv[i-1]=b=b*i%M
def dfs1(v,p):
    s=1
    l=[]
    c1,c2=[1],[1]
    for w in e[v]:
        if w==p:continue
        l+=w,
        dfs1(w,v)
        u=sz1[w]
        c1+=c1[-1]*dp1[w]*inv[u]%M,
        s+=u
    for w in l[::-1]:
        c2+=c2[-1]*dp1[w]*inv[sz1[w]]%M,
    e[v]=l
    c[v]=c1,c2[::-1]
    sz1[v]=s
    dp1[v]=c1[-1]*fac[s-1]%M
n,*t=open(0).read().split()
n=int(n)
e=[[]for _ in range(n)]
for a,b in zip(*[map(int,t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
sz1,sz2=[0]*n,[0]*n
dp1,dp2=[0]*n,[0]*n
c=[[]for _ in range(n)]
dfs1(0,-1)
# print(dp1)
sz2[0]=1
dp2[0]=1
s=[0]
while s:
    v=s.pop()
    l=len(e[v])
    c1,c2=c[v]
    uv=sz2[v]-1
    tv=dp2[v]*inv[uv]
    for i,w in enumerate(e[v]):
        tw=c1[i]*c2[i+1]%M
        uw=uv+sz1[v]-sz1[w]-1
        dp2[w]=tv*tw*fac[uw]%M
        sz2[w]=uw+2
        s+=w,
# print(dp2)
for i in range(n):
    u1=sz1[i]-1
    u2=sz2[i]-1
    print(dp1[i]*dp2[i]*inv[u1]*inv[u2]*fac[u1+u2]%M)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
M=10**9+7
N=10**6
fac=[0]*(N+1)
fac[0]=b=1
for i in range(1,N+1):fac[i]=b=b*i%M
inv=[0]*(N+1)
inv[N]=b=pow(fac[N],M-2,M)
for i in range(N,0,-1):inv[i-1]=b=b*i%M
def dfs1(v,p):
    s=1
    l=[]
    c1,c2=[1],[1]
    for w in e[v]:
        if w==p:continue
        l+=w,
        dfs1(w,v)
        u=sz1[w]
        c1+=c1[-1]*dp1[w]*inv[u]%M,
        s+=u
    for w in l[::-1]:
        c2+=c2[-1]*dp1[w]*inv[sz1[w]]%M,
    e[v]=l
    c[v]=c1,c2[::-1]
    sz1[v]=s
    dp1[v]=c1[-1]*fac[s-1]%M
n,*t=open(0).read().split()
n=int(n)
e=[[]for _ in range(n)]
for a,b in zip(*[map(int,t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
sz1,sz2=[0]*n,[0]*n
dp1,dp2=[0]*n,[0]*n
c=[[]for _ in range(n)]
dfs1(0,-1)
# print(dp1)
sz2[0]=1
dp2[0]=1
s=[0]
while s:
    v=s.pop()
    l=len(e[v])
    c1,c2=c[v]
    uv=sz2[v]-1
    tv=dp2[v]*inv[uv]
    for i,w in enumerate(e[v]):
        tw=c1[i]*c2[i+1]%M
        uw=uv+sz1[v]-sz1[w]-1
        dp2[w]=tv*tw*fac[uw]%M
        sz2[w]=uw+2
        s+=w,
# print(dp2)
for i in range(n):
    u1=sz1[i]-1
    u2=sz2[i]-1
    print(dp1[i]*dp2[i]*inv[u1]*inv[u2]*fac[u1+u2]%M)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
words = []
for i in range(n):
    words.append(input())

counter = 0
for i in range(n):
    for j in range(i+1, n):
        if sorted(words[i]) == sorted(words[j]):
            counter += 1

print(counter)

### FIXED CODE ###

# -*- coding: utf-8 -*-

def my_sort(word):
    sorted_word_list = sorted(word)
    sorted_word = ""
    for letter in sorted_word_list:
        sorted_word += letter
    return sorted_word

n = int(input())
words = {}
for i in range(n):
    word = my_sort(input())
    if word in words.keys():
        words[word] += 1
    else:
        words[word] = 1

for key in words.keys():
    words[key] = max(words[key]*(words[key]-1)//2, 0)

print(sum(words.values()))
### BUGGY CODE ###

# 解説AC
from collections import deque

N = int(input())
edge = [[] for _ in range(N)]
for n in range(N - 1):
    a,b = map(int, input().split())
    edge[a-1].append([b-1, n])
    edge[b-1].append([a-1, n])

def bfs(s:int, g:int):
    """ 始点sから終点gまでのパスを求める """
    path = [0] * N
    visited = [False] * N
    flag = False # 終点到着フラグ
    
    que = deque([s])
    visited[s] = True
    while que:
        v = que.popleft()
        for w, n in edge[v]:
            if visited[w]: continue
            path[w] = path[v] | (1 << n) # パスを記録
            if w == g: # 終点到着
                flag = True
                break
            que.append(w)
        if flag: break
    return path[g]

M = int(input())
path = [0] * M # 各制約で使用するパス
for i in range(M):
    u,v = map(int, input().split())
    path[i] = bfs(u - 1, v - 1)

ans = 0
# 包除原理
for bit in range(1 << M):
    val = 0
    for i in range(M):
        if (bit >> i) & 1:
            val |= path[i]
    if bin(bit).count("1") % 2 == 0:
        ans += 1 << (N - 1 - bin(val).count("1"))
    else:
        ans -= 1 << (N - 1 - bin(val).count("1"))

print(ans)

### FIXED CODE ###

# 解説AC
from collections import deque

N = int(input())
edge = [[] for _ in range(N)]
for n in range(N - 1):
    a,b = map(int, input().split())
    edge[a-1].append([b-1, n])
    edge[b-1].append([a-1, n])

def bfs(s:int, g:int):
    """ 始点sから終点gまでのパスを求める """
    in_edge = [-1] * N
    par = [-1] * N
    flag = False # 終点到着フラグ
    
    que = deque([s])
    while que:
        v = que.popleft()
        for w, n in edge[v]:
            if w == par[v]: continue
            in_edge[w] = n
            par[w] = v
            if w == g:
                flag = True
                break
            que.append(w)
        if flag: break
    path = 0
    cur = g
    while in_edge[cur] >= 0:
        path |= 1 << in_edge[cur]
        cur = par[cur]
    return path


M = int(input())
path = [0] * M # 各制約で使用するパス
for i in range(M):
    u,v = map(int, input().split())
    path[i] = bfs(u - 1, v - 1)

ans = 0
# 包除原理
for bit in range(1 << M):
    val = 0
    for i in range(M):
        if (bit >> i) & 1:
            val |= path[i]
    if bin(bit).count("1") % 2 == 0:
        ans += 1 << (N - 1 - bin(val).count("1"))
    else:
        ans -= 1 << (N - 1 - bin(val).count("1"))

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

from collections import deque

s = input()
d = deque()
li = list(s)
for i in li:
    d.append(i)
n = int(input())
for _ in range(n):
    q = input().split()
    if (len(q)==1):
        d.reverse()
    else:
        a = int(q[1])
        b = q[2]
        if (a == 1):
            d.appendleft(b)
        else:
            d.append(b)
ans = list(d)
xxx = "".join(ans)
print(xxx)

### FIXED CODE ###

from collections import deque

s = input()
d = deque(s)
n = int(input())
flag = 0
for _ in range(n):
    q = input().split()
    if (len(q)==1):
        if(flag == 0):
            flag = 1
        else:
            flag = 0
    else:
        a = int(q[1])
        b = q[2]
        if (a == 1):
            if flag==0:
                d.appendleft(b)
            else:
                d.append(b)
        else:
            if flag==0:
                d.append(b)
            else:
                d.appendleft(b)

if flag==1:
    d.reverse()
ans = list(d)
xxx = "".join(ans)
print(xxx)
### BUGGY CODE ###

def digitSum(n):
    # 数値を文字列に変換
    s = str(n)
    # １文字ずつ数値化し配列にする。
    array = list(map(int, s))
    # 合計値を返す
    return sum(array)
S = input()
Scount = 0
for i in range(len(S)-1):
    for j in range(1,len(S)):
        if (i+j)<=len(S):
            part_S = S[i:i+j]
            num = int(part_S)
            sum3 = digitSum(num)
            while sum3 != digitSum(sum3):
                sum3 = digitSum(sum3)
            if sum3 == 3 or sum3 == 6 or sum3 ==9:
                num = num // 3
                if num % 673==0:
                    Scount += 1
print(Scount)

### FIXED CODE ###

S = input()
from collections import defaultdict
d = defaultdict(int)
before = 0
for i in range(1,len(S)+1):
    now = (int(S[-i])*pow(10,i,2019)+before) % 2019
    d[now] += 1
    before = now
d[0] += 1
ans = 0
for i in d.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

mod = 998244353

class BIT:
	def __init__(self, n):
		self.n = n
		self.nums = [0] * (n+1)
		
	def add(self, i, x):
		n, nums = self.n, self.nums
		i += 1
		while i <= n:
			nums[i] += x
			i += i & -i
	
	def sum(self, i):
		nums = self.nums
		s = 0
		i += 1
		while i:
			s += nums[i]
			i -= i & -i
		return s

N, K = rl()
lr = []
for i in range(K):
	l, r = rl()
	lr.append((l,r))

bit = BIT(N+1)
bit.add(1, 1)
bit.add(2, -1)

ans = 0
for i in range(1, N+1):
	s = bit.sum(i)
	#print('s', s)
	for k in range(K):
		l, r = lr[k]
		if i+l <= N:
			#print('l', i+l, s)
			bit.add(i+l, s)
			if i+r+1 <= N:
				#print('r', i+r+1, -s)
				bit.add(i+r+1, -s)
			else:
				ans += s
				ans %= mod
print(ans)
#print(bit.sum(N) % mod)


### FIXED CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

mod = 998244353

N, K = rl()
lr = []
for i in range(K):
	l, r = rl()
	lr.append((l,r))
lr.sort()

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

ans = 0
s = 0
flags = [1] * K
for i in range(1, N+1):
	s += dp[i]
	s %= mod
	for k in range(K):
		if flags[k] == 0:
			break
		l, r = lr[k]
		if i+l <= N:
			dp[i+l] += s
			if i+r+1 <= N:
				dp[i+r+1] -= s
			else:
				ans += s
				ans %= mod
				break
		else:
			flags[k] = 0
			break
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from numpy import bitwise_or
from bisect import bisect, insort

def inpl(): 
    return tuple(map(int, input().split()))

N, K = inpl()
numbers = []

for _ in range(N):
    A, B = inpl()
    numbers.append([A, B])


res = 0

target = bin(K)[2:]
targets = [target]
while "10" in target:
    n = target.rfind("10")
    new_target = target[:n] + "0" + "1"*(len(target)-n-1)
    targets.append(new_target)
    target = new_target

targets = list(map(int, targets, [2]*len(targets)))

for target in targets:
    tmp = 0
    for a, b in numbers:
        if bitwise_or(target, a) == target:
            tmp += b
    res = max(res, tmp)
print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
def inpl(): 
    return tuple(map(int, input().split()))

N, K = inpl()
numbers = []

for _ in range(N):
    A, B = inpl()
    numbers.append([A, B])
res = 0

target = bin(K)[2:]
targets = [target]
while "10" in target:
    n = target.rfind("10")
    new_target = target[:n] + "0" + "1"*(len(target)-n-1)
    targets.append(new_target)
    target = new_target

targets = list(map(int, targets, [2]*len(targets)))

for target in targets:
    tmp = 0
    for a, b in numbers:
        if (target | a) == target:
            tmp += b
    res = max(res, tmp)
print(res)