CodeEff/ECCO huggingface dataset:
# Original solution
n,t = list(map(int,input().split()))
a = [int(i) for i in input().split()]
ans = t
for i in range(n-1):
    if abs(a[i+1] - a[i]) > t:
        ans += t
    else:
        ans += abs(a[i+1] - a[i])

print(ans)

# Optimized solution
n,t = list(map(int,input().split()))
a = [int(i) for i in input().split()]
ans = t
for i in range(n-1):
    ans += min(abs(a[i+1] - a[i]), t)
print(ans)
# Original solution
N,T=list(map(int,input().split()))
t=list(map(int,input().split()))
a=T
for i in range(N-1):
  a+=min(T,t[i+1]-t[i])
print(a)

# Optimized solution
N,T=list(map(int,input().split()))
t=list(map(int,input().split()))
a=[min(T,t[i+1]-t[i]) for i in range(N-1)]
print((sum(a)+T))
# Original solution
_,T,*t=list(map(int,open(0).read().split()));print((sum(min(T,j-i)for i,j in zip(t,t[1:]))+T))

# Optimized solution
_,T,*t=list(map(int,open(0).read().split()));print((sum(min(T,j-i)for i,j in zip([-T]+t,t))))
# Original solution
n,T,*t=list(map(int,open(0).read().split()));print((T+sum(min(j-i,T)for i,j in zip(t,t[1:]))))

# Optimized solution
_,T,b,*t=list(map(int,open(0).read().split()))
a=T
for i in t:a+=min(i-b,T);b=i
print(a)
# Original solution
def main():
    N, T = list(map(int, input().split()))
    t = list(map(int, input().split()))
    c = t[-1] + T + 1
    a = [0 for _ in range(c)]
    for i in t:
        a[i] += 1
        a[i+T] -= 1

    count = 0
    for i in range(c):
        if(0 < i):
            a[i] += a[i - 1]
            if(a[i] != 0): count += 1

    if(a[0] != 0): count += 1
    print(count)
    return 0

if __name__ == '__main__':
    main()

# Optimized solution
n, t = list(map(int, input().split()))
T = list(map(int, input().split()))

ans = t
for t1, t2 in zip(T[:-1], T[1:]):
  ans += min(t2 - t1, t)

print(ans)
# Original solution
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n,t=list(map(int,input().split()))
T=list(map(int,input().split()))
ans=t
for i in range(1,n):
    ans+=min(T[i]-T[i-1],t)
print(ans)

# Optimized solution
n,t=list(map(int,input().split()))
T=list(map(int,input().split()))
ans=t
for i in range(1,n):
    ans+=min(T[i]-T[i-1],t)
print(ans)
# Original solution
from sys import stdin


def main():
    lines = stdin.readlines()
    T = int(lines[0].split()[1])
    tn = [int(ti) for ti in lines[1].split()]
    ans = 0
    for t1, t2 in zip(tn[0:], tn[1:]):
        ans += min(T, t2 - t1)
    ans += T
    print(ans)
    return


main()


# Optimized solution
from sys import stdin


def main():
    lines = stdin.readlines()
    T = int(lines[0].split()[1])
    tn = [int(ti) for ti in lines[1].split()]
    print((tn[-1] + T - sum(t2 - t1 - T for t1, t2 in zip(tn[0:], tn[1:]) if t2 - t1 > T)))
    return


main()
# Original solution
n, T = list(map(int, input().split()))
t = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    x = t[i+1]-t[i]
    if x < T:
        ans += x
    else:
        ans += T
print((ans+T))

# Optimized solution
n, T = list(map(int, input().split()))
t = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    x = t[i+1]-t[i]
    ans += min(x, T)
print((ans+T))
# Original solution
#N,Tの取得
l = list(map(int, input().split()))
N = l[0]
T = l[1]

#秒のリストを取得
tl = list(map(int, input().split()))

sw = 0 #スイッチオンオフの管理
bt = 0 #直前のスイッチを押した時間
gt = 0 #秒数総和
for i, t in enumerate(tl):
    if sw == 1 and t - bt > T:
        sw = 0 #全快スイッチを押してからT秒経過していたら、スイッチオフ
    if sw == 0:
        gt += T #スイッチオフの時はT秒追加
    else:
        gt += t - bt  #スイッチがオンのとき、前回からの経過時間を加算
    bt = t
    sw = 1 #スイッチオン。
        

print((str(gt)))

# Optimized solution
#N,Tの取得
l = list(map(int, input().split()))
N = l[0]
T = l[1]

#秒のリストを取得
tl = list(map(int, input().split()))

bt = 0 #直前のスイッチを押した時間
gt = T #秒数総和
for t in tl[1:]:
    if t - bt > T:
        gt += T #スイッチオフの時はT秒追加
    else:
        gt += t - bt #スイッチがオンのとき、前回からの経過時間を加算
    bt = t
        

print((str(gt)))
# Original solution
#N,Tの取得
l = list(map(int, input().split()))
N = l[0]
T = l[1]

#秒のリストを取得
tl = list(map(int, input().split()))

bt = 0 #直前のスイッチを押した時間
gt = T #秒数総和
for t in tl[1:]:
    if t - bt > T:
        gt += T #スイッチオフの時はT秒追加
    else:
        gt += t - bt #スイッチがオンのとき、前回からの経過時間を加算
    bt = t
        

print((str(gt)))

# Optimized solution
#N,Tの取得
N,T = list(map(int, input().split()))
#秒のリストを取得
tl = list(map(int, input().split()))

bt = 0 #直前のスイッチを押した時間
gt = T #秒数総和
for t in tl[1:]:
    if t - bt > T:
        gt += T #スイッチオフの時はT秒追加
    else:
        gt += t - bt #スイッチがオンのとき、前回からの経過時間を加算
    bt = t

print((str(gt)))
# Original solution
n, T= list(map(int, input().split()))
t = list(map(int, input().split()))
total = T
for i in range(1, n):
    if t[i]-t[i-1]>=T:
        total += T
    else:
        total += t[i]-t[i-1]
print(total)

# Optimized solution
n, T= list(map(int, input().split()))
t = list(map(int, input().split()))
total = T
for i in range(1, n):
    total += min(T, t[i]-t[i-1])
print(total)
# Original solution
def LI(): return [int(x) for x in input().split(" ")]
def LS(): return [str(x) for x in input().split(" ")]
def ItoS(L): return [str(x) for x in L]
def StoI(L): return [int(c) for c in L]


def solve():
    n, t = LI()
    T = LI()
    sentou = [0 for _ in range(T[-1] + t + 1)]

    i = 0
    while i < len(T):
        sentou[T[i]] += 1
        sentou[T[i] + t] -= 1
        i += 1

    j = 1
    while j < len(sentou):
        sentou[j] += sentou[j - 1]
        j += 1

    print((n * t - (sum(sentou) - (sentou.count(1) + len(sentou) - sentou.count(1) - sentou.count(0)))))

solve()

# Optimized solution
def LI(): return [int(x) for x in input().split(" ")]
def LS(): return [str(x) for x in input().split(" ")]
def ItoS(L): return [str(x) for x in L]
def StoI(L): return [int(c) for c in L]


def solve():
    n, t = LI()
    T = LI()

    ans = 0
    for i in range(len(T) - 1):
        ans += min(t, T[i + 1] - T[i])

    print((ans + t))


solve()
# Original solution
def c_Sentou(N, T, t):
    ans = 0
    for i in range(N):
        if i == N - 1:
            ans += T
            continue
        ans += min(T, t[i + 1] - t[i])
    return ans

N,T = [int(i) for i in input().split()]
t = [int(i) for i in input().split()]
print((c_Sentou(N, T, t)))

# Optimized solution
def c_sentou(N, T, time):
    time.append(float('inf'))  # 番兵
    ans = 0
    for i in range(N):
        ans += min(T, time[i + 1] - time[i])
    return ans

N,T = [int(i) for i in input().split()]
time = [int(i) for i in input().split()]
print((c_sentou(N, T, time)))
# Original solution
def c_sentou(N, T, Times):
    times = Times + [Times[-1] + T]  # 番兵を追加(最後の人が押したT秒後に止まる)
    return sum([min(T, times[i + 1] - times[i]) for i in range(N)])

N, T = [int(i) for i in input().split()]
Time = [int(i) for i in input().split()]
print((c_sentou(N, T, Time)))

# Optimized solution
def c_sentou():
    N, T = [int(i) for i in input().split()]
    Times = [int(i) for i in input().split()] + [float('inf')]  # 番兵追加
    return sum([min(T, Times[i + 1] - Times[i]) for i in range(N)])

print((c_sentou()))
# Original solution
def resolve():

    n,t=list(map(int,input().split()))
    T=list(map(int,input().split()))
    ans=t
    for i in range(1,n):
        if T[i]-T[i-1]>t:
            ans+=t
        else:
            ans+=T[i]-T[i-1]
    print(ans)




resolve()

# Optimized solution

def resolve():

    n,t=list(map(int,input().split()))
    T=list(map(int,input().split()))
    T.append(T[-1]+10**10)
    ans=0
    for i in range(n):
        if T[i+1]-T[i]>t:
            ans+=t
        else:
            ans+=T[i+1]-T[i]
    print(ans)




resolve()
# Original solution
from collections import deque
N, M = list(map(int, input().split()))
X = list(map(int, input().split()))
EDGE = [list(map(int, input().split())) for i in range(M)]
EDGE.sort(key=lambda x:x[2])

EDGELIST = [[] for i in range(N+1)]
for i in range(M):
    x, y, w = EDGE[i]
    EDGELIST[x].append(i)
    EDGELIST[y].append(i)

Group = [i for i in range(N+1)]

def find(x):
    while Group[x] != x:
        x = Group[x]
    return x

def Union(x, y):
    if find(x) != find(y):
        Group[find(y)] = Group[find(x)] = min(find(y), find(x))

USE = [0]*M
WEIGHTSUM = [0] + [X[i] for i in range(N)]

QUE = deque()

for i in range(M):
    x, y, w = EDGE[i]

    if find(x) != find(y):
        WEIGHTSUM[find(x)] = WEIGHTSUM[find(y)] = WEIGHTSUM[find(x)] + WEIGHTSUM[find(y)]
        Union(x, y)

    if w <= WEIGHTSUM[find(x)]:
        QUE.append(i)

while QUE:
    q = QUE.pop()
    x, y, w = EDGE[q]

    NQUE = deque([q])

    while NQUE:
        nq = NQUE.pop()

        if USE[nq] == 1:
            continue

        x, y, _ = EDGE[nq]
        for e in EDGELIST[x] + EDGELIST[y]:
            if EDGE[e][2] <= w:
                NQUE.append(e)
        USE[nq] = 1

print((USE.count(0)))



# Optimized solution
import sys
input = sys.stdin.readline
from collections import deque
N, M = list(map(int, input().split()))
X = list(map(int, input().split()))
EDGE = [list(map(int, input().split())) for i in range(M)]
EDGE.sort(key=lambda x:x[2])

EDGELIST = [[] for i in range(N+1)]
for i in range(M):
    x, y, w = EDGE[i]
    EDGELIST[x].append(i)
    EDGELIST[y].append(i)

Group = [i for i in range(N+1)]

def find(x):
    while Group[x] != x:
        x = Group[x]
    return x

def Union(x, y):
    if find(x) != find(y):
        Group[find(y)] = Group[find(x)] = min(find(y), find(x))

USE = [0]*M
WEIGHTSUM = [0] + [X[i] for i in range(N)]

QUE = deque()

for i in range(M):
    x, y, w = EDGE[i]

    if find(x) != find(y):
        WEIGHTSUM[find(x)] = WEIGHTSUM[find(y)] = WEIGHTSUM[find(x)] + WEIGHTSUM[find(y)]
        Union(x, y)

    if w <= WEIGHTSUM[find(x)]:
        QUE.append(i)

while QUE:
    q = QUE.pop()
    x, y, w = EDGE[q]

    NQUE = deque([q])

    while NQUE:
        nq = NQUE.pop()

        if USE[nq] == 1:
            continue

        x, y, _ = EDGE[nq]
        for e in EDGELIST[x] + EDGELIST[y]:
            if EDGE[e][2] <= w:
                NQUE.append(e)
        USE[nq] = 1

print((USE.count(0)))
# Original solution
import sys
sys.setrecursionlimit(10**6)

N, M = list(map(int, input().split()))
*X, = list(map(int, input().split()))
E = []
for i in range(M):
    a, b, y = list(map(int, input().split()))
    E.append((y, a-1, b-1))
E.sort()

*p, = list(range(N))
Z = [0]*M
A = X[:]
C = [-1]*N
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y

def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
        A[px] += A[py]
    else:
        p[px] = py
        A[py] += A[px]
    return 1

G = [None for i in range(M)]

ans = 0
for i, (y, a, b) in enumerate(E):
    pa = root(a); pb = root(b)
    ca = C[pa]; cb = C[pb]
    if unite(a, b):
        pa = root(a)
        Z[i] = 1
        C[pa] = i
        #print(">", i, pa, pb, A[pa], y)
        if A[pa] < y:
            G[i] = []
            if ca != -1:
                G[i].append(ca)
            if cb != -1:
                G[i].append(cb)
    else:
        if A[pa] < y:
            G[i] = []
            if ca != -1:
                G[i].append(ca)
            C[pa] = i

sx = sum(X)
#print(Z)

if N > 1:
    from collections import deque
    que = deque()
    if sx < E[C[0]][0]:
        que.append(C[0])
    #print(G, C)
    while que:
        v = que.popleft()
        #print(v)
        if G[v] is not None:
            ans += 1
            for w in G[v]:
                que.append(w)
print(ans)

# Optimized solution
from collections import deque
import operator

N, M = list(map(int, input().split()))
*X, = list(map(int, input().split()))
E = []
for i in range(M):
    a, b, y = list(map(int, input().split()))
    E.append((y, a-1, b-1))
E.sort()
*Y, = list(map(operator.itemgetter(0), E))

*p, = list(range(N))
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y

A = X[:]
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
        A[px] += A[py]
    else:
        p[px] = py
        A[py] += A[px]
    return 1

G = [[] for i in range(M)]
B = [0]*M
C = [-1]*N

ans = 0
for i, (y, a, b) in enumerate(E):
    pa = root(a); pb = root(b)
    ca = C[pa]; cb = C[pb]
    if unite(a, b):
        if ca != -1:
            G[i].append(ca)
        if cb != -1:
            G[i].append(cb)
        pa = root(a)
    else:
        if ca != -1:
            G[i].append(ca)
    B[i] = A[pa]
    C[pa] = i

if N > 1 and sum(X) < E[C[0]][0]:
    que = deque()
    que.append(C[0])
    while que:
        v = que.popleft()
        if B[v] < Y[v]:
            ans += 1
            que.extend(G[v])
print(ans)
# Original solution

def solve():
    MOD = 998244353
    N, K = list(map(int, input().split()))
    S = set()
    for i in range(K):
        _l, _r = list(map(int, input().split()))
        _s = set(list(range(_l, _r+1)))
        S |= _s

    # dp[i] : iに到達する経路数
    dp = [0] * (N+1)
    dp[1] = 1
    for i in range(2, N+1):
        for d in S:
            if i-d > 0:
                dp[i] = (dp[i] + dp[i-d]) % MOD
    print((dp[N]))


solve()


# Optimized solution

def solve():
    MOD = 998244353
    N, K = list(map(int, input().split()))
    LR_L = [[int(x) for x in input().split()] for y in range(K)]
    # S = set()
    # for i in range(K):
    #     _l, _r = map(int, input().split())
    #     _s = set(list(range(_l, _r+1)))
    #     S |= _s

    # dp[i] : iに到達する経路数
    dp = [0] * (N+1)
    dp[1] = 1
    dp[2] = -1
    for i in range(1, N+1):
        dp[i] += dp[i-1]
        dp[i] %= MOD
        # for d in S:
        #     if i-d > 0:
        #         dp[i] = (dp[i] + dp[i-d]) % MOD
        for li, ri in LR_L:
            if i + li < N+1:
                dp[i+li] += dp[i]
                dp[i+li] %= MOD
            if i + ri + 1 < N+1:
                dp[i+ri+1] -= dp[i]
                dp[i+ri+1] %= MOD
    print((dp[N]))


solve()
# Original solution
N,K=list(map(int,input().split()))
MOD = 998244353
dp = [0]*(N+1)

LR = []
for _ in range(K):
    l, r = list(map(int, input().split()))
    LR.append((l,r))

LR.sort()
dp[1] = 1
dp_sum = [0]*(N+1) # dp[i]の累積和
dp_sum[1] = 1

for i in range(2, N+1):
    for l, r in LR:
        if i - l >= 1:
            dp[i] += dp_sum[i-l] - dp_sum[max(0, i-r-1)]
            dp[i] %= MOD
    dp[i] %= MOD
    dp_sum[i] = dp_sum[i-1] + dp[i]
        
print((dp[N]%MOD))

# Optimized solution
N,K=list(map(int,input().split()))
MOD = 998244353
dp = [0]*(N*3)

LR = []
for _ in range(K):
    l, r = list(map(int, input().split()))
    LR.append((l,r))

LR.sort()

imos = [0]*(N*3)
dp[1] = 1
imos[1] = 1
for i in range(1, N):
    if i >= 2:
        dp[i+1] += dp[i]

    for l, r in LR:
        dp[i+l] += dp[i]
        dp[i+l] %= MOD
        dp[i+r+1] -= dp[i]
        dp[i+r+1] %= MOD
    
    

print((dp[N]%MOD))
# Original solution
N, K = [int(v) for v in input().split()]

links = []
for k in range(K):
    L, R = [int(v) for v in input().split()]
    links.append((L, R))

links = sorted(links, key=lambda x: x[1])

count = [1]
sub = [0, 1]
subtotal = 1

for i in range(1, N):
    v = 0
    for l, r in links:
        r2 = i - l + 1
        l2 = i - r
        if l2 < 0:
            l2 = 0
        if r2 >= 0:
            v += sub[r2] - sub[l2]

    count.append(v % 998244353)
    subtotal += v
    sub.append(subtotal)

print((count[-1]))


# Optimized solution
N, K = [int(v) for v in input().split()]

links = []
for k in range(K):
    L, R = [int(v) for v in input().split()]
    links.append((L, R))

links = sorted(links, key=lambda x: x[1])

count = [1]
sub = [0, 1]
subtotal = 1

for i in range(1, N):
    v = 0
    for l, r in links:
        r2 = i - l + 1
        l2 = i - r
        if l2 < 0:
            l2 = 0
        if r2 >= 0:
            v += sub[r2] - sub[l2]

    count.append(v % 998244353)
    subtotal = (subtotal + v) % 998244353
    sub.append(subtotal )

print((count[-1]))
# Original solution
import sys
sys.setrecursionlimit(10 ** 9)

n,k = list(map(int,input().split()))
s = []
for i in range(k):
  l,r = list(map(int,input().split()))
  s.append((l,r))
MOD = 998244353

memo = [-1 for _ in range(n+1)]

def f(x):
  if x < 1:
    return 0
  if x == 1:
    return 1
  if memo[x] != -1:
    return memo[x]
  res = 0
  for l,r in s:
    for i in range(l,r+1):
      res += f(x-i)
      res %= MOD
  memo[x] = res
  return res

print((f(n)))


# Optimized solution
import sys
sys.setrecursionlimit(10 ** 9)

n,k = list(map(int,input().split()))
s = []
for i in range(k):
  l,r = list(map(int,input().split()))
  s.append((l,r))
s.sort()
MOD = 998244353

memo = [-1 for _ in range(n+1)]

def f(x):
  if x < 1:
    return 0
  if x == 1:
    return 1
  if memo[x] != -1:
    return memo[x]
  res = 0
  for l,r in s:
    for i in range(l,r+1):
      res += f(x-i)
      res %= MOD
  memo[x] = res
  return res

print((f(n)))
# Original solution
def main():
    n, k = list(map(int, input().split()))
    mod = 998244353
    dp = [0] * (n + 1)
    dp[1] = 1
    delta = []
    for _ in range(k):
        l, r = list(map(int, input().split()))
        for i in range(l, r + 1):
            delta.append(i)
    delta.sort()
    for i in range(n):
        for d in delta:
            if i + d > n:
                break
            dp[i + d] += dp[i]
            dp[i + d] %= mod
    print((dp[n]))


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    n, k = list(map(int, input().split()))
    mod = 998244353
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = -1
    left = [0] * k
    right = [0] * k
    for i in range(k):
        left[i], right[i] = list(map(int, input().split()))
        right[i] += 1
    for i in range(1, n + 1):
        dp[i] += dp[i - 1]
        for j in range(k):
            if i + left[j] <= n:
                dp[i + left[j]] += dp[i]
            if i + right[j] <= n:
                dp[i + right[j]] -= dp[i]
        dp[i] %= mod
    print((dp[n]))


if __name__ == '__main__':
    main()
# Original solution
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353

n, k = list(map(int, input().split()))
dp = [0] * n
dp[0] = 1
dp[1] = -1
delta = []
for _ in range(k):
    l, r = list(map(int, input().split()))
    delta.append((l, 1))
    delta.append((r+1, -1))

total = 0
for i in range(n):
    total += dp[i]
    for p, d in delta:
        if i + p >= n:
            continue
        dp[i + p] += total * d
print((total % MOD))

# Optimized solution
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353

n, k = list(map(int, input().split()))
dp = [0] * n
dp[0] = 1
dp[1] = -1
delta = []
for _ in range(k):
    l, r = list(map(int, input().split()))
    delta.append((l, 1))
    delta.append((r+1, -1))

total = 0
for i in range(n):
    total += dp[i]
    total %= MOD
    for p, d in delta:
        if i + p >= n:
            continue
        dp[i + p] += total * d
        dp[i + p] %= MOD
print((total % MOD))
# Original solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

N, K = mapint()
mod = 998244353
dp = [0]*N
dp[0] = 1

ok = [0]*(N+1)
for _ in range(K):
    l, r = mapint()
    ok[l-1] += 1
    ok[r] -= 1
from itertools import accumulate
ok = list(accumulate(ok))
lis = [i for i in range(1, N+1) if ok[i-1]]
for i in range(N):
    for d in lis:
        if i-d>=0:
            dp[i] += dp[i-d]
            dp[i] %= mod

print((dp[-1]))

# Optimized solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

N, K = mapint()
mod = 998244353
dp = [0]*(N+1)
dp[1] = 1

Ks = [list(mapint()) for _ in range(K)]
Ks.sort()

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sums(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

bit = Bit(N)
bit.add(1, 1)

for i in range(2, N+1):
    for l, r in Ks:
        if i-l<0:
            break
        dp[i] += bit.sums(i-l) - bit.sums(max(0, i-r-1))
        dp[i] %= mod
    bit.add(i, dp[i])

print((dp[-1]))
# Original solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

N, K = mapint()
mod = 998244353
dp = [0]*(N+1)
dp[1] = 1

Ks = [list(mapint()) for _ in range(K)]
Ks.sort()

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sums(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

bit = Bit(N)
bit.add(1, 1)

for i in range(2, N+1):
    for l, r in Ks:
        if i-l<0:
            break
        dp[i] += bit.sums(i-l) - bit.sums(max(0, i-r-1))
        dp[i] %= mod
    bit.add(i, dp[i])

print((dp[-1]))

# Optimized solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

N, K = mapint()
dp = [0]*(N*3+1)
dp[1] = 1
dp[2] = -1
mod = 998244353
LR = [list(mapint()) for _ in range(K)]
for i in range(1, N+1):
    dp[i] = (dp[i]+dp[i-1])%mod
    for l, r in LR:
        dp[i+l] = (dp[i+l]+dp[i])%mod
        dp[i+r+1] = (dp[i+r+1]-dp[i])%mod

print((dp[N]))
# Original solution

N, K = list(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]))


# Optimized solution

N, K = list(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]))
# Original solution
# coding:UTF-8
import sys
from math import factorial

MOD = 998244353
INF = 10000000000

def main():
    n, k = list(map(int, input().split()))  # スペース区切り連続数字
    lrList = [list(map(int, input().split())) for _ in range(k)]  # スペース区切り連続数字(行列)

    s = []
    for l, r in lrList:
        for i in range(l, r+1):
            s.append(i)

    Interm = [0] * (n + 1)
    Interm[0] = 0
    Interm[1] = 1
    for i in range(1, n+1):
        if i >= 2:
            for j in s:
                if n - j >= 1:
                    Interm[i] = (Interm[i] + Interm[i - j]) % 998244353

    result = Interm[n]
    # ------ 出力 ------#
    print(("{}".format(result)))

if __name__ == '__main__':
    main()


# Optimized solution
# coding:UTF-8
import sys
from math import factorial

MOD = 998244353
INF = 10000000000

def main():
    n, k = list(map(int, input().split()))  # スペース区切り連続数字
    lrList = [list(map(int, input().split())) for _ in range(k)]  # スペース区切り連続数字(行列)

    s = []
    for l, r in lrList:
        for i in range(l, r+1):
            s.append(i)
    s.sort()

    sum = [0] * (n + 1)
    Interm = [0] * (2 * n + 1)
    sum[1] = 1
    for i in range(1, n):
        for j in range(k):
            l, r = lrList[j][0], lrList[j][1]
            Interm[i+l] += sum[i]
            Interm[i+r+1] -= sum[i]
        sum[i+1] = (sum[i] + Interm[i+1]) % MOD

    # result = Interm[n]
    result = (sum[n] - sum[n-1]) % MOD
    # ------ 出力 ------#
    print(("{}".format(result)))

if __name__ == '__main__':
    main()