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

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

wt  = [0] * (n+1)
val = [0] * (n+1)

for i in range(0,n):
    wt[i], val[i] = list(map(int,input().split()))

def knapSack(W, wt, val, n): 
    K = [[0 for x in range(W+1)] for x in range(n+1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n+1): 
        for w in range(W+1): 
            if i==0 or w==0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
  
    return K[n][W] 
  
print(knapSack(W, wt, val, n))

### FIXED CODE ###

# DP
def main():
    N, W = map(int, input().split())
 
    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))
 
 
main()
### BUGGY CODE ###

N,X=map(int,input().split())
def f(n):
    if n==0:
        return [1]
    else:
        return [0]+f(n-1)+[1]+f(n-1)+[0]
print(sum(f(N)[i] for i in range(X)))

### FIXED CODE ###

N,X=map(int,input().split())
H=[1]
P=[1]

for i in range(N):
    H.append(H[i]*2+3)
    P.append(P[i]*2+1)

def f(n,x):
    if n==0:
        return  1
    else:
        if x==1:
            return 0
        elif x<2+H[n-1]:
            return f(n-1,x-1)
        elif x==2+H[n-1]:
            return P[n-1]+1
        elif x<H[n]:
            return P[n-1]+f(n-1,x-H[n-1]-2)+1
        elif x==H[n]:
            return P[n]
print(f(N,X))
### BUGGY CODE ###

n, m = map(int, input().split())
s = list(sorted(map(int, input().split())))

for i in range(m):
  num = s[-1]
  s.pop(-1)
  s.append(num//2)
  s.sort()

print(sum(s))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
s = list(map(lambda x: x* (-1), map(int, input().split())))

heapq.heapify(s)

while m != 0:
  num = heapq.heappop(s)
  heapq.heappush(s, -1*num//2*-1)
  m -= 1

print(-1 * sum(s))
### BUGGY CODE ###

A,B,X = map(int,input().split())
ans = 0
for a in range(A,B+1):
    if a%X==0:
        ans += 1
print(ans)

### FIXED CODE ###

a,b,x = map(int, raw_input().split())

first = a/x
if a%x > 0 : first += 1
last = b/x
ans = last - first + 1
print ans
### BUGGY CODE ###

import numpy as np

n = int(input())
map_ = {}
memo = []

for i in range(n):
  a = int(input())
  if a not in memo:
    map_.update({str(a):1})
    memo.append(a)
  else:
    map_[str(a)] += 1
list_ = np.array([i%2 for i in list(map_.values())])

print(np.sum(list_))

### FIXED CODE ###

n = int(input())
a_list = [int(input()) for _ in range(n)]

my_set = set()
for i in a_list:
  if i in my_set:
    my_set.remove(i)
  else:
    my_set.add(i)
print(len(my_set))
### BUGGY CODE ###

H, W = list(map(int, input().split()))
grid = []
for _ in range(H):
    grid.append(list(input()))

queue = [(0, 0, 1)]
while queue:
    h, w, cnt = queue.pop(0)
    grid[h][w] = cnt
    nexts = [(h+1, w, cnt+1), (h-1, w, cnt+1), (h, w+1, cnt+1), (h, w-1, cnt+1)]
    for y, x, c in nexts:
        if 0 <= y and y < H and 0 <= x and x < W:
            if grid[y][x] == '#':
                continue
            elif grid[y][x] == '.':
                queue.append((y, x, c))
            elif c < grid[y][x]:
                queue.append((y, x, c))

if grid[-1][-1] == '.' or grid[-1][-1] == '#':
    print(-1)
    exit() 

sharp_num = 0
max_num = 0
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            sharp_num += 1
print(H * W - grid[-1][-1] - sharp_num)





### FIXED CODE ###

import sys
from collections import deque
 
h,w = map(int, sys.stdin.readline().split())
maze = [list(sys.stdin.readline()) for _ in range(h)]
dis = [[-1 for _ in range(w)] for _ in range(h)]
 
que = deque()
que.append((0,0))
dis[0][0] = 1
 
while que:
    y,x = que.popleft()
    for dx, dy in ((1,0), (0,1), (-1, 0), (0, -1)):
        nx = x + dx
        ny = y + dy
        if (nx < 0) or (nx > w-1) or (ny < 0) or (ny > h-1): continue
        if (maze[ny][nx] == '.') and (dis[ny][nx] == -1):
            dis[ny][nx] = dis[y][x] + 1
            que.append((ny, nx))
 
ans = 0
black_num = 0
for m in maze:
    black_num += m.count('#')
 
if dis[h-1][w-1] == -1:
    ans = -1
else:
    ans = w*h - black_num - dis[h-1][w-1]
 
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
m = [[0] * W for _ in range(H)]
for h in range(H):
    i = None
    for j in range(W + 1):
        if j < W and S[h][j] == ".":
            if i is None:
                i = j
        else:
            if i is not None:
                for k in range(i, j):
                    m[h][k] += j - i
                i = None
for w in range(W):
    i = None
    for j in range(H + 1):
        if j < H and S[j][w] == ".":
            if i is None:
                i = j
        else:
            if i is not None:
                for k in range(i, j):
                    m[k][w] += j - i
                i = None
ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        ans = max(ans, m[h][w] - 1)
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
m = [[0] * W for _ in range(H)]
for h in range(H):
    i = None
    for j in range(W + 1):
        if j < W and S[h][j] == ".":
            if i is None:
                i = j
        else:
            if i is not None:
                for k in range(i, j):
                    m[h][k] += j - i
                i = None
for w in range(W):
    i = None
    for j in range(H + 1):
        if j < H and S[j][w] == ".":
            if i is None:
                i = j
        else:
            if i is not None:
                for k in range(i, j):
                    m[k][w] += j - i
                i = None
ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        ans = max(ans, m[h][w] - 1)
print(ans)
### BUGGY CODE ###

N=50000+1
p=[True]*N
p[0],p[1]=False,False
for i in xrange(2,int(N**0.5)+1):
    if p[i]==True:
        for j in xrange(i**2,N,i):
            p[j]=False
while True:
    n=input()
    if n==0:break
    c=0
    for i in xrange(n/2+1):
        if p[i] and p[n-i]:c+=1
    print c

### FIXED CODE ###

import itertools
N=50000+1
p=[True]*N
p[0],p[1]=False,False
for i in xrange(2,int(N**0.5)+1):
    if p[i]==True:
        for j in xrange(i**2,N,i):
            p[j]=False
plist=[i for i in xrange(N) if p[i]]
c=[0]*N*2
for i,j in itertools.combinations(plist,2):
    c[i+j]+=1
for i in xrange(N):
    if p[i]:c[i+i]+=1
while True:
    n=input()
    if n==0:break
    print c[n]
### BUGGY CODE ###

from itertools import groupby

N = int(input())
def fast_prime_factorization(n):
    # 素因数分解（ロー法）  O(n^(1/4) polylog(n))
    from subprocess import Popen, PIPE
    return list(map(int, Popen(["factor", str(n)], stdout=PIPE).communicate()[0].split()[1:]))

def a(n):
    if n == 1:
        return 1
    f = fast_prime_factorization(n if n%2 else 2*n)
    step = max(v ** len(list(gr)) for v, gr in groupby(f))
    for m in range(step, 2*n, step):
        if m * (m-1) // 2 % n == 0:
            return m-1
        if m * (m+1) // 2 % n == 0:
            return m

print(a(N))


### FIXED CODE ###

from itertools import groupby

N = int(input())
def fast_prime_factorization(n):
    # 素因数分解（ロー法）  O(n^(1/4) polylog(n))
    from subprocess import Popen, PIPE
    return list(map(int, Popen(["factor", str(n)], stdout=PIPE).communicate()[0].split()[1:]))


def egcd(a, b):
    # 拡張ユークリッド互除法
    # ax + by = gcd(a,b)の最小整数解を返す
    # 最大公約数はg
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def a(n):
    if n == 1:
        return 1
    f = fast_prime_factorization(2*n)
    f2 = [v ** len(list(gr)) for v, gr in groupby(f)]
    l = len(f2)
    ans = 1<<62
    for s in range(1<<l):
        p = 1
        q = 1
        for i in range(l):
            if s>>i & 1:
                p *= f2[i]
            else:
                q *= f2[i]
        if p==1 or q==1:
            continue
        g, x, y = egcd(-p, q)
        a = abs(y) * q
        #print(p, q, x, y, a)
        if ans > a:
            ans = a
    return ans

#print(a(15**12))

print(a(N))
### BUGGY CODE ###

A,B = map(int,input().split())
def cf(x1,x2):
  cf=[]
  for i in range(2,min(x1,x2)+1):
    if x1 % i == 0 and x2 % i == 0:
      cf.append(i)
  return cf

cf_list = cf(A,B)
p = []
for num in cf_list:
  for n in range(2,num):
    if num%n == 0:
      break
  else:
    p.append(num)
print(len(p)+1)

  

### FIXED CODE ###

import fractions
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])


    return arr

A,B = map(int,input().split())
print(len(factorization(fractions.gcd(A,B)))+1)
### BUGGY CODE ###

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

    inf = 10**18
    res = a[0]
    for i in range(1,n):
        res *= a[i]
    if res > inf:
        print(-1)
        return 0
    else:
        print(res)

if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    n = int(input())
    a = sorted(list(map(int,input().split())),reverse=True)

    inf = 10**18
    res = a[0]
    if 0 in a:
        print(0)
        return 0
    for i in range(1,n):
        res *= a[i]
        if res > inf:
            print(-1)
            return 0

    if res > inf:
        print(-1)
        return 0
    else:
        print(res)

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

import collections

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

ans = {}
# 全てのキーに対して処理を実施
for k in c.keys():
  cnt = 0
  for l in c.keys():
    if (k == l):
      cnt += int((c[l]-1)*(c[l]-2)/2)
    else:
      cnt += int(c[l]*(c[l]-1)/2)
  ans[k] = cnt

for i in range(n):
  print(ans[a[i]])

### FIXED CODE ###

import collections

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

ans = {}
comb = 0
# 全てのキーに対して処理を実施
for k in c.keys():
  comb += int(c[k]*(c[k]-1)/2)
for k in c.keys():
  ans[k] = comb-(c[k]-1)

for i in range(n):
  print(ans[a[i]])
### BUGGY CODE ###

from collections import deque
n = int(input())
deq = deque()
sub_deq = {}
for i in range(n):
    cmd = input()
    if cmd == 'deleteFirst':
        while deq:
            data = deq.pop()
            if data[1]:
                data[1] = 0
                break
    elif cmd == 'deleteLast':
        while deq:
            data = deq.popleft()
            if data[1]:
                data[1] = 0
                break
    else:
        cmd, val = cmd.split()
        if cmd == 'insert':
            data = [val, 1]
            deq.append(data)
            if val not in sub_deq:
                sub_deq[val] = [data]
            else:
                sub_deq[val].append(data)
        elif cmd == 'delete':
            if val in sub_deq:
                deq_v = sub_deq[val]
                while deq_v:
                    data = deq_v.pop()
                    if data[1]:
                        data[1] = 0
                        break
print(*(data[0] for data in reversed(deq) if data[1]))

### FIXED CODE ###

from collections import deque
import sys
n = int(input())
deq = deque()
sub_deq = {}
for cmd in sys.stdin.readlines():
    if cmd == 'deleteFirst\n':
        while deq:
            data = deq.pop()
            if data[1]:
                data[1] = 0
                break
    elif cmd == 'deleteLast\n':
        while deq:
            data = deq.popleft()
            if data[1]:
                data[1] = 0
                break
    else:
        cmd, val = cmd.split()
        if cmd == 'insert':
            data = [val, 1]
            deq.append(data)
            if val not in sub_deq:
                sub_deq[val] = [data]
            else:
                sub_deq[val].append(data)
        elif cmd == 'delete':
            if val in sub_deq:
                deq_v = sub_deq[val]
                while deq_v:
                    data = deq_v.pop()
                    if data[1]:
                        data[1] = 0
                        break
sys.stdout.write(" ".join(data[0] for data in reversed(deq) if data[1]))
sys.stdout.write('\n')
### BUGGY CODE ###

from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

const = 10 ** 9 + 7
MAX = 10 ** 5 + 50

#エラトステネス
L = [1 for i in range(100001)]
L[0] = 0
L[1] = 0
plist = []
for i in range(100001):
	if L[i] == 1:
		plist.append(i)
		c = 2
		while True:
			if i * c <= 100000:
				L[i * c] = 0
				c += 1
			else:
				break

#組み合わせ、逆元前計算
fac = [0] * (MAX)
inv = [0] * (MAX)
finv = [0] * (MAX)
fac[0], fac[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1

for i in range(2, MAX):
	fac[i] = fac[i - 1] * i % const
	inv[i] = inv[const % i] * (const - (const // i)) % const
	finv[i] = finv[i - 1] * inv[i] % const

#受け取り、処理
N, M = getlist()
if M == 1:
	print(1)
else:
	D = defaultdict(int)
	while M != 1:
		for i in plist:
			if M % i == 0:
				D[i] += 1
				M = M // i
				break

	data = []
	for i in D:
		data.append(D[i])

	#計算
	ans = 1
	for i in data:
		ans *= fac[i + N - 1] * finv[i] * finv[N - 1]
		ans %= const
	print(ans)

### FIXED CODE ###

from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

const = 10 ** 9 + 7
MAX = 10 ** 5 + 50

#エラトステネス
L = [1 for i in range(100001)]
L[0] = 0
L[1] = 0
plist = []
for i in range(100001):
	if L[i] == 1:
		plist.append(i)
		c = 2
		while True:
			if i * c <= 100000:
				L[i * c] = 0
				c += 1
			else:
				break

#組み合わせ、逆元前計算
fac = [0] * (MAX)
inv = [0] * (MAX)
finv = [0] * (MAX)
fac[0], fac[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1

for i in range(2, MAX):
	fac[i] = fac[i - 1] * i % const
	inv[i] = inv[const % i] * (const - (const // i)) % const
	finv[i] = finv[i - 1] * inv[i] % const

#受け取り、処理
N, M = getlist()
if M == 1:
	print(1)
else:
	D = defaultdict(int)
	while M != 1:
		judge = "No"
		for i in plist:
			if M % i == 0:
				D[i] += 1
				M = M // i
				judge = "Yes"
				break
		if judge == "No":
			D[M] += 1
			break

	data = []
	for i in D:
		data.append(D[i])

	#計算
	ans = 1
	for i in data:
		ans *= fac[i + N - 1] * finv[i] * finv[N - 1]
		ans %= const
	print(ans)
### BUGGY CODE ###

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

tree = [set([i]) for i in range(N+1)]
points = [0] * N

for i in range(1, N):
  a, b = map(int, input().split())
  tree[a].add(b)
  for j in range(i):
    if a in tree[j]:
      tree[j].add(b)
      
for i in range(Q):
  p, x = map(int, input().split())
  for node in tree[p]:
    points[node-1] += x

# print(tree)
    
for point in points:
  print(point, end=" ")

### FIXED CODE ###

n,q = map(int,input().split())
rl = [0] * n
scores = [0] * n
for i in range(n-1):
    a,b = map(int,input().split())
    rl[b-1] = a-1
for j in range(q):
    p,x = map(int,input().split())
    scores[p-1] += x
for k in range(1,n):
    scores[k] += scores[rl[k]]
print(*scores)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [(2 ** (leng - j - 1)) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()   




### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [pow(2,leng - 1 - j, mod) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from sys import stdin
def problem(firstline, thereafter):
    N, M = firstline.strip().split()
    N = int(N)
    M = int(M)
    points = []
    for i in thereafter:
        a, b = i.strip().split()
        points.append((int(b),int(a)))
    points.sort(reverse=True)
    days = {}
    for i in range(M, -1 , -1):
        days[i] = 0
    for i in points:
        if i[1] <= M:
            for j in range(M - i[1], -1, -1):
                if not days[j]:
                    days[j] = i[0]
                    break
    out = 0
    for i, values in days.items():
        out += values
    return out





def main():
    print(problem(stdin.readline(), stdin.readlines()))

main()


### FIXED CODE ###

import heapq

def main():
    n, m = map(int, input().split())
    data = {}
    priorityQ = []
    for _ in range(n):
        a, b = map(int, input().split())
        if m + 1 - a >= 0:
            if m+1-a in data:
                data[m+1-a].append(b)
            else:
                data[m+1-a] = [b]
    ans = 0
    for i in range(m, 0, -1):
        if i in data.keys():
            for k in data[i]:
                heapq.heappush(priorityQ, -k)
        if priorityQ:
            ans -= heapq.heappop(priorityQ)
    print(ans)
    return

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

s=input()
n=len(s)
dp=[[0]*(13) for _ in range(n)]
mod=10**9+7

for i in range(n):
    if i==0:
        if s[i]=='?':
            for j in range(10):
                dp[i][j]=1
        else:
            x=int(s[i])
            dp[i][x]=1
    else:
        if s[i]=='?':
            for k in range(10):
                for j in range(13):
                    dp[i][(j*10+k)%13]+=dp[i-1][j]
                    dp[i][(j*10+k)%13]%=mod
        else:
            x=int(s[i])
            for j in range(13):
                dp[i][(j*10+x)%13]+=dp[i-1][j]
                dp[i][(j*10+x)%13]%=mod
print(dp[n-1][5]%mod)

### FIXED CODE ###

s=input()
n=len(s)
dp=[[0]*(13) for _ in range(n)]
mod=10**9+7

for i in range(n):
    if i==0:
        if s[i]=='?':
            for j in range(10):
                dp[i][j]=1
        else:
            x=int(s[i])
            dp[i][x]=1
    else:
        if s[i]=='?':
            for k in range(10):
                for j in range(13):
                    dp[i][(j*10+k)%13]+=dp[i-1][j]
                    dp[i][(j*10+k)%13]%=mod
        else:
            x=int(s[i])
            for j in range(13):
                dp[i][(j*10+x)%13]+=dp[i-1][j]
                dp[i][(j*10+x)%13]%=mod
print(dp[n-1][5]%mod)
### BUGGY CODE ###

N = int(input())
for i in range(1, N+1):
    ans = 0
    for x in range(1, i//2):
        for y in range(1, i//2):
            for z in range(1, i//2):
                tmp = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if tmp == i:
                    ans += 1
    print(ans)

### FIXED CODE ###

N = int(input())

ans = [0 for _ in range(10**4+50)]

for x in range(1, 105):
    for y in range(1, 105):
        for z in range(1, 105):
            tmp = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if tmp < 10**4+50:
                ans[tmp] += 1

for i in range(1, N+1):
    print(ans[i])
### BUGGY CODE ###

mod = 10**9+7

# N = 15
N = int(input())
xx = list(map(int, input().split()))

a = 1
for i in range(2,N):
    a *= i
    # a %= mod

aa = [a]
for i in range(N-2):
    aa.append((aa[-1]+a*pow(i+2,mod-2,mod))%mod)


dx = [xx[i]-xx[i-1] for i in range(1,N)]

ans = 0
for a,d in zip(aa,dx):
    ans += a*d
    ans %= mod

print(ans%mod)


### FIXED CODE ###

mod = 10**9+7

# N = 15
N = int(input())
xx = list(map(int, input().split()))

a = 1
for i in range(2,N):
    a *= i
    a %= mod

aa = [a]
for i in range(N-2):
    aa.append((aa[-1]+a*pow(i+2,mod-2,mod))%mod)


dx = [xx[i]-xx[i-1] for i in range(1,N)]

ans = 0
for a,d in zip(aa,dx):
    ans += a*d
    ans %= mod

print(ans%mod)
### BUGGY CODE ###

def around(K,A):
    N2 = A.pop(0)
    A.append(N2+K)
    return A

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

X = 0
X_min = 1000000000
for j in range(0,len(A)):
    X=0
#     print(A)
    X = A[len(A)-1] - A[0]
#     print(X)
#     for i in range(0,len(A)-1): #i番目の家からスタート
#         X += A[i+1] - A[i]
#         if X > X_min:
#             i=0
#             break
#     if i == len(A)-2:
#     print(X)
    if X_min > X:
        X_min = X
    A=around(K,A)
#     print(X_min)
    
print(X_min)

### FIXED CODE ###

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

X = 0
space = 0
idx = 0
A.append(A[0]+K)
for j in range(0,len(A)-1):
    X=0
    X = A[j+1] - A[j]
    if space < X:
        space = X
        idx = j
    
print(A[idx] + K - A[idx+1] )
### BUGGY CODE ###

n,m=map(int,input().split())
s=[0]*n
for _ in range(m):
    b,c=map(int,input().split())
    for i in range(b-1,c):
        s[i]+=1
print(s.count(m))

### FIXED CODE ###

n,m=map(int,input().split())
s=[0]*n
max_=1
min_=n
for _ in range(m):
    b,c=map(int,input().split())
    if b>max_:
        max_=b
    if c<min_:
        min_=c
if min_<max_:
  print('0')
else:
  print(min_-max_+1)