Harryxun/stf_run huggingface dataset:
def main():
    B_MAX = (80 + 80 - 1) * 80 // 2
    H, W = list(map(int, input().split(' ')))
    A = [list(map(int, input().split(' '))) for _ in range(H)]
    B = [list(map(int, input().split(' '))) for _ in range(H)]
    dp = [[[0 for _ in range(B_MAX + 1)] for _ in range(W)] for _ in range(H)]
    dp[0][0][abs(A[0][0] - B[0][0])] = 1
    max_b = abs(A[0][0] - B[0][0])
    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            d = abs(A[h][w] - B[h][w])
            max_b += d
            for b in range(max_b + 1):
                v = 0
                if h > 0:
                    v = max(v, dp[h - 1][w][abs(b - d)])
                    if b + d <= B_MAX:
                        v = max(v, dp[h - 1][w][b + d])
                if w > 0:
                    v = max(v, dp[h][w - 1][abs(b - d)])
                    if b + d <= B_MAX:
                        v = max(v, dp[h][w - 1][b + d])
                dp[h][w][b] = v
    ans = 0
    while dp[H - 1][W - 1][ans] == 0:
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    B_MAX = (80 + 80 - 1) * 80 // 2
    H, W = list(map(int, input().split(' ')))
    A = [list(map(int, input().split(' '))) for _ in range(H)]
    B = [list(map(int, input().split(' '))) for _ in range(H)]
    dp = [[[0 for _ in range(B_MAX + 1)] for _ in range(W)] for _ in range(H)]
    dp[0][0][abs(A[0][0] - B[0][0])] = 1
    max_b = abs(A[0][0] - B[0][0])
    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            d = abs(A[h][w] - B[h][w])
            max_b += d
            for b in range(min(B_MAX, max_b) + 1):
                v = 0
                if h > 0:
                    v = max(v, dp[h - 1][w][abs(b - d)])
                    if b + d <= B_MAX:
                        v = max(v, dp[h - 1][w][b + d])
                if w > 0:
                    v = max(v, dp[h][w - 1][abs(b - d)])
                    if b + d <= B_MAX:
                        v = max(v, dp[h][w - 1][b + d])
                dp[h][w][b] = v
    ans = 0
    while dp[H - 1][W - 1][ans] == 0:
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()
N = int(input())
A = list(map(int, input().split()))

if 0 in A:
    print(0)
    return

ans = 1
for a in A:
    ans *= a
    if ans > 1000000000000000000:
        print(-1)
        return

print(ans)

### FIXED CODE ###

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

    if 0 in A:
        print(0)
        return

    ans = 1
    for a in A:
        ans *= a
        if ans > 1000000000000000000:
            print(-1)
            return

    print(ans)

main()
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = 10**9+7
pos = [*filter(lambda x: x >= 0, A)]
neg = [*filter(lambda x: x < 0, A)]
pos.sort(reverse=True)
neg.sort()

ans = 1
i,j = 0,0
while i+j < K:
    flag = True
    if i == len(pos):
        flag = False
    elif j == len(neg):
        flag = True
    elif pos[i] >= -neg[j]:
        flag = True
    else:
        flag = False

    if flag:
        ans = ans * pos[i] % m
        i += 1
    else:
        ans = ans * neg[j] % m
        j += 1
if j % 2 == 0 or N==K:
    print(ans)
elif len(pos) == 0:
    ans = 1
    for i in range(K):
        ans = ans * neg[len(neg)-1-i] % m
    print(ans)
else:
    flag = True
    if i >= len(pos)-1:
        flag = False
    elif j >= len(neg)-1:
        flag = True
    elif pos[i]*pos[i+1] >= neg[j]*neg[j+1]:
        flag = True
    else:
        flag = False

    if flag:
        ans = ans * pow(neg[j],m-2,m) % m
        ans = ans * pos[i+1] % m
    else:
        ans = ans * pow(pos[i],m-2,m) % m
        ans = ans * neg[j+1] % m
    print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
m = 10**9+7
pos = [*filter(lambda x: x>=0, A)]
neg = [*filter(lambda x: x<0, A)]
pos.sort(reverse=True)
neg.sort()

ans = 1
i,j = 0,0# 使った数
while i+j < K:
    flag = True
    if i == len(pos):
        flag = False
    elif j == len(neg):
        flag = True
    elif pos[i] >= -neg[j]:
        flag = True
    else:
        flag = False

    if flag:
        ans = ans * pos[i] % m
        i += 1
    else:
        ans = ans * neg[j] % m
        j += 1

if j % 2 == 0 or N==K:
    print(ans)
elif len(pos) == 0:
    ans = 1
    for i in range(K):
        ans = ans * neg[len(neg)-1-i] % m
    print(ans)
else:
    flag2 = True
    if i == 0:
        flag2 = True
    elif j == 0:
        flag2 = False
    elif i == len(pos):
        flag2 = False
    elif j == len(neg):
        flag2 = True
    elif pos[i-1]*pos[i] > neg[j-1]*neg[j]:# = を抜いた
        flag2 = True
    else:
        flag2 = False

    if flag2:
        ans = ans * pow(neg[j-1],m-2,m) % m
        ans = ans * pos[i] % m
    else:
        ans = ans * pow(pos[i-1],m-2,m) % m
        ans = ans * neg[j] % m
    print(ans)
a=input()
b=input()
c=input()

print('bust'if a+b+c>=22 else 'win')

### FIXED CODE ###

a=input()
lst = [int(e) for e in a.split(' ')]

print('bust'if sum(lst)>=22 else 'win')
import math

#引数nが素数かどうかを判定
def is_prime(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n%i == 0:
            return False
    return True

def getPrimeExp(n):
    array = [True]*(n+1)
    result = []
    for i in range(2, n+1):
        if array[i]:
            array[i] = False
            result.append(i)
            for j in range(2, n+1):
                ij = i**j
                if ij <= n and array[ij]:
                    result.append(ij)
                    array[ij] = False
                elif ij > n:
                    break
            for j in range(i*2, n+1, i):
                array[j] = False

            # for j in range(2, n):
            #     ij = i**j
            #     if ij <= n:
            #         result.append(ij)
            #         array[ij] = False
    return sorted(result)

N = int(input())
if is_prime(N):
    print(1)
else:
    cnt = 0
    primeExp = getPrimeExp(N) 
    n = N
    # print(primeExp)
    for z in primeExp:
        if n%z == 0:
            n = int(n/z)
            cnt += 1
    print(cnt)

### FIXED CODE ###

import math

# 素数か否かを判定する関数
def is_prime(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n%i == 0:
            return False
    return True      

# nまでの素数を返す関数（エラトステネスの篩）
def getPrime(n):
    n_sqrt = int(math.sqrt(n))
    array = [True]*(n_sqrt+1)
    result = []
    for i in range(2, n_sqrt+1):
        if array[i]:
            array[i] = False
            result.append(i)
            for j in range(i*2, n_sqrt+1, i):
                array[j] = False
    return result

N = int(input())
n = N
prime = getPrime(n)
prime_exp = []
# print(prime)
for p in prime:
    cnt = 0
    while n%p == 0:
        n = int(n/p)
        # print(n)
        cnt += 1
    if cnt != 0:
        prime_exp.append([p, cnt])
if is_prime(n) and n != 1:
    prime_exp.append([n, 1])
ans = 0
for pe in prime_exp:
    ans += int((-1+math.sqrt(1+8*pe[1]))/2)
print(ans)
from scipy.special import comb, factorial

try:
  n, k = tuple(map(int, input().split(' ')))
  for i in range(1, k+1):
    print(comb(k-1, i-1, exact=True) * (factorial(n-k+1, exact=True) // (factorial(n-k-i+1, exact=True) * factorial(i, exact=True))) % (10 ** 9 + 7))
except Exception as e:
  print(e)

### FIXED CODE ###

input_str = input()
items = set(list(input_str))
print('Yes' if len(items) == 2 and len(list(input_str.replace(list(items)[0], ''))) == 2 else 'No')
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
res_arr = [-1] * n

for i in a:
    res_arr[i] = 0

for i in range(1, n):
    if res_arr[i] == 0:
        next
    elif i == 1:
        res_arr[i] = 1
    elif i == 2:
        res_arr[i] = 1 + res_arr[i-1]
    else:
        res_arr[i] = res_arr[i-1] + res_arr[i-2]

res = res_arr[-1]+res_arr[-2]
if n == 1:
    res = res_arr[1]
elif n == 2:
    res = 1 + res_arr[1]
amari = res % 1000000007
print(amari)


### FIXED CODE ###

arr = list(map(int, input().split()))
arr.sort()
print(arr[0]+arr[1])
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    def euclid(a, b):
        if b == 0:
            return a
        else:
            return euclid(b, a % b)

    def multiple(a, b):
        return a * b // euclid(a, b)

    n, m = ns()
    s = list(input())
    t = list(input())

    gcd = multiple(n, m)

    s_idx = [gcd // n * i for i in range(n)]
    t_idx = [gcd // m * i for i in range(m)]

    ans = ["@"] * (gcd + 2)
    for i, si in enumerate(s_idx):
        ans[si] = s[i]
    for i, ti in enumerate(t_idx):
        if ans[ti] != "@" and ans[ti] != t[i]:
            print(-1)
            exit(0)
    print(gcd)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    def euclid(a, b):
        if b == 0:
            return a
        else:
            return euclid(b, a % b)

    def multiple(a, b):
        return a * b // euclid(a, b)

    n, m = ns()
    s = list(input())
    t = list(input())

    gcd = multiple(n, m)

    s_idx = [gcd // n * i for i in range(n)]
    t_idx = [gcd // m * i for i in range(m)]
    t_set = set(t_idx)

    for idx in s_idx:
        if idx in t_set:
            if s[idx * n // gcd] != t[idx * m // gcd]:
                print(-1)
                exit(0)

    print(gcd)


if __name__ == '__main__':
    main()
import heapq

n = int(input())
rev_g = [[] for _ in range(n+1)]
for i in range(n-1):
    a = int(input())
    rev_g[a].append(i+2)

def f(v):
    if len(rev_g[v]) == 0:
        return 0
    q = []
    for nv in rev_g[v]:
        heapq.heappush(q, f(nv))
    max_count = 0
    max_num = -1
    while q:
        num = heapq.heappop(q)
        if max_num == num:
            max_count += 1
        else:
            max_num += max_count
            max_count = 0
            if num > max_num:
                max_num = num
            elif num == max_num:
                max_count = 1
            else:
                heapq.heappush(q, max_num)
                max_num = num
                max_count = 0
    return max_num + max_count + 1

print(f(1))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n = int(input())
rev_g = [[] for _ in range(n+1)]
for i in range(n-1):
    a = int(input())
    rev_g[a].append(i+2)

def f(v):
    m = len(rev_g[v])
    if m == 0:
        return 0
    q = []
    for nv in rev_g[v]:
        q.append(f(nv))
    q.sort()
    dp = [0] * (m+1)
    for i in range(m):
        dp[i+1] = max(q[i]+1, dp[i]+1)
    return dp[m]


print(f(1))
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
a = list( map(int, input().split()))
b = list( map(int, input().split()))
d = [0]*n

for i in range(n):
    d[i] = a[i]-b[i]

d.sort()

if sum(d)<0:
    print(-1)
    exit()

cnt_neg = 0
for i in range(n):
    if d[i]<0:cnt_neg+=1

if cnt_neg==0:
    print(0)
    exit()
else:
    ans = cnt_neg

last=n-1
for neg in range(n):
    print(d)
    if d[neg]>=0:break

    while d[neg]<0:
        tmp = min(-d[neg], d[last])
        d[neg] += tmp
        d[last] -= tmp
        if d[last] == 0:
            last-=1
            ans+=1

if d[last] != a[last]-b[last] and d[last]!=0 : ans+=1

print(ans)


### FIXED CODE ###

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

n = int(input())
a = list( map(int, input().split()))
b = list( map(int, input().split()))
d = [0]*n

for i in range(n):
    d[i] = a[i]-b[i]

d.sort()

if sum(d)<0:
    print(-1)
    exit()

cnt_neg = 0
for i in range(n):
    if d[i]<0:cnt_neg+=1

if cnt_neg==0:
    print(0)
    exit()
else:
    ans = cnt_neg

last=n-1
for neg in range(n):
    if d[neg]>=0:break

    while d[neg]<0:
        tmp = min(-d[neg], d[last])
        d[neg] += tmp
        d[last] -= tmp
        if d[last] == 0:
            last-=1
            ans+=1

if d[last] != a[last]-b[last] and d[last]!=0 : ans+=1

print(ans)
3 4 5


### FIXED CODE ###

a, b, c = (int(i) for i in input().split())
print(a*b//2)
r=input()
k=r.split()

t1=t2=0
for i in range(k[1]):
    t1 += k[0]
for i in range(k[0]):
    t2 += k[1]
    
jj=[t1,t2]
jj.sort(reverse=True)
print(jj[0])

### FIXED CODE ###

r = input()
k=r.split()
if k[0] == k[1]:
    print('Yes')
else:
    print('No')
import math
N = int(input())
ans = float("inf")

for i in range(1,int(math.sqrt(N))):
    if N%i == 0:
        ans = min(ans,i+N/i-2)
print(int(ans))


### FIXED CODE ###

import math
N = int(input())
ans = float("inf")

for i in range(1,int(math.sqrt(N))+1):
    if N%i == 0:
        ans = min(ans,i+N//i-2)
print(int(ans))
import sys
from fractions import Fraction

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def a(s):
	r = Fraction(s)
	return r.numerator, r.denominator



def main():
	n = int(input())
	#b , c = tin()
	al = [a(input()) for _ in range(n)]
	ret = 0
	for i, (vin, vid) in enumerate(al):
		for (vjn, vjd) in al[i+1:]:
			if (vin*vjn) % (vid, vjd)==0:
				ret += 1
	return ret
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
#from fractions import Fraction
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def a(s):
	if s.count('.')==0:
		n2=0
		n5=0
		v = int(s)
	else:
		p = s.index('.')
		n2 = -(len(s) - p - 1)
		n5 = -(len(s) - p - 1)
		if p == 1 and s[0]=='0':
			v= int(s[2:])
		else:
			v = int(s[:p]+s[p+1:])
	while v % 2 == 0:
		v = v//2
		n2+=1
	while v % 5 == 0:
		v = v//5
		n5+=1
	return str(n2)+'_'+str(n5)

def main():
	n = int(input())
	#b , c = tin()
	al = [a(input()) for _ in range(n)]
	cal = collections.Counter(al)
	#pa(cal)
	ret = 0
	pp = set()
	for k in cal:
		for k2 in cal:
			if k+'_'+k2 in pp:
				continue
			#pa((vi*vj)/(10**20))
			if k==k2:
				a2, a5 = map(int, k.split('_'))
				if a2>=0 and a5 >= 0:
					ret += cal[k]*(cal[k]-1)//2
			else:
				a2, a5 = map(int, k.split('_'))
				b2, b5 = map(int, k2.split('_'))
				if a2+b2 >= 0 and a5+b5 >= 0:
					ret += cal[k]*cal[k2]
				
			pp.add(k+'_'+k2)
			pp.add(k2+'_'+k)
			#pa((k,k2,ret))
			
	return ret
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
def f(K, S):
    #ここに処理を書いてください
    res = 0
    for i in range(K+1):
      for j in range(K+1):
        if i + j <= S and S-i-j <= K:
          res += 1
    return res

in = list(map(int, input().split()))
print(f(in[0], in[1]))

### FIXED CODE ###

def f(K, S):
    #ここに処理を書いてください
    res = 0
    for i in range(K+1):
      for j in range(K+1):
        if i + j <= S and S-i-j <= K:
          res += 1
    return res

inx = list(map(int, input().split()))
print(f(inx[0], inx[1]))
N, W = map(int, input().split())
P = []
for i in range(N):
  P.append(list(map(int, input().split())))

#dp[i][w] : i番目までの品物で、wの重みでできる最大の価値. 1-indexed
dp = [[0] * (W+1) for i in range(N+1)]

for i in range(1,N+1):
  weight = P[i-1][0]
  value = P[i-1][1]

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

#print(dp)
print(max(dp[N][:]))

### FIXED CODE ###

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

W1,V1 = map(int, input().split())

P = {W1:[V1], W1+1:[], W1+2:[], W1+3:[]}

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

PS={}
for k,v in P.items():
  v.sort(reverse=True)
  S = [0] * (len(v)+1)
  for i in range(len(v)):
    S[i+1] = S[i] + v[i]
  PS[k] = S
  
#print(P)
#print(PS)
A,B,C,D = len(PS[W1]), len(PS[W1+1]), len(PS[W1+2]), len(PS[W1+3])
ans = 0
for a in range(A):
  for b in range(B):
    for c in range(C):
      for d in range(D):
        if a*W1 + b*(W1+1) + c*(W1+2) + d*(W1+3) > W:
          continue
        ans = max(ans, PS[W1][a] + PS[W1+1][b] + PS[W1+2][c] + PS[W1+3][d])
        
print(ans)
n = int(input())
ans = 0
for i in range(n):
   l, r = map(int, input().split())
   del = r-l
   ans += del

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(n):
   l, r = map(int, input().split())
   ans += r-l+1

print(ans)
import sys
def input(): return sys.stdin.readline().rstrip()
def rec(v):
    if dp[v]!=-1:return dp[v]
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    dp[v]=res
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global dp,graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    dp=[-1]*n #頂点i(0-)を始点としたときの有効パスの長さの最大値
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
def rec(v):
    if dp[v]!=-1:return dp[v]
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    dp[v]=res
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global dp,graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    dp=[-1]*n #頂点i(0-)を始点としたときの有効パスの長さの最大値
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()
n=int(input())
k=int(input())

x=list(map(int,input().split()))
a=0
for i in range(n):
  a+=min(x[i]*2,(k-x[i])*2)
  
print(a)
  

### FIXED CODE ###

one_side=input()
oneside=int(one_side)
whole=oneside**2
white_side=input()
whiteside=int(white_side)
print(whole-whiteside)
A, B, K = map(int, input().split())
a=[]
b=[]
if A>=B:
  for i in range(1,A+1): # i = [1,2,3,4,....A]
    if A%i==0 and B%i==0:
      a.append( A/i )
      b.append( B/i )
  
else:
  for i in range(1,B+1): # i = [1,2,3,4,....A]
    if A%i==0 and B%i==0:
      a.append( A/i )
      b.append( B/i )

c=[]
for ea in a:
  if ea in b:
    c.append( ea )

print(c[K])
    


### FIXED CODE ###

A, B, K = map(int, input().split())
a=[]
#b=[]
if A>=B:
  for i in range(1, A+1): # i = [1,2,3,4,....A]
    if A%i==0 and B%i==0:
      a.append( i )
      # b.append( B/i )
  
else:
  for i in range(1, B+1): # i = [1,2,3,4,....A]
    if A%i==0 and B%i==0:
      a.append( i )
      # b.append( B/i )

#print(a)
#print(b)

#c=[]
#for ea in a:
 # if ea in b:
  #  c.append( ea )
c=len(a)
print(a[c-K])
from numba import jit

import sys
sys.setrecursionlimit(10**9)

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

MOD = 998244353
for _ in range(K):
    L, R = map(int, input().split())
    S |= set(range(L, R + 1))
# print(f'{S=}')

DP = [-1] * (N + 1)
DP[0] = 0
DP[1] = 1


@njit
def f(idx):
    ans = 0
    for s in S:
        if idx - s < 0:
            continue
        if DP[idx - s] == -1:
            DP[idx - s] = f(idx - s)
        ans += DP[idx - s]
    return ans % MOD


ans = f(N)
# print(f'{DP=}')
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 998244353
LR = []
for _ in range(K):
    L, R = map(int, input().split())
    LR.append((L, R))
# print(f'{LR=}')

DP = [0] * (N + 1)
DP[1] = 1
S = [0] * (N + 1)

for i in range(1, len(DP)):
    for L, R in LR:
        v = S[max(i - L, 0)] - S[max(i - R - 1, 0)]
        DP[i] += v
    DP[i] %= MOD
    S[i] = (S[i - 1] + DP[i]) % MOD

# print(f'{DP=}')
# print(f'{S=}')
print(DP[-1])
N = int(input())
C = [0]

prev = -1
for _ in range(N):
    c = int(input())
    if c == prev:
        continue
    else:
        C.append(c)
        prev = c

MOD = 10**9+7
dp = [0]*(N+4)
last = [-1]*(N+4)
dp[0] = 1
for i in range(1, len(C)):
    if last[C[i]] == -1:
        last[C[i]] = i
        dp[i] = dp[i-1]
    else:
        dp[i] = dp[i-1]+dp[last[C[i]]]
        dp[i] %= MOD
        last[C[i]] = i
print(max(dp))


### FIXED CODE ###

N = int(input())
C = [-1]

for _ in range(N):
    c = int(input())
    if c == C[-1]:
        continue
    else:
        C.append(c)

MOD = 10**9+7
dp = 1
prev = [0]*(max(C)+1)

for c in C[1:]:
    dp = (dp+prev[c]) % MOD
    prev[c] = dp
print(dp)
n=int(input())
list=[]
for i in range(n):
  list=list.append(int(input())
a=0
for j in range(n):
  if max(list[:j])<=list[j]:
    a=a+1
  else:
    pass
print(a)

### FIXED CODE ###

n=int(input())
list=list(map(int,input().split()))
a=1
for j in range(n-1):
  if max(list[:j+1])<=list[j+1]:
    a=a+1
  else:
    pass
print(a)
n, m = map(int, input().split())

if n == m:
  print('Yes'):
else:
  print('No')

### FIXED CODE ###

n, m = map(int, input().split())
 
if n == m:
  print('Yes')
else:
  print('No')
import sys
p = [r for r in sys.stdin.read().split('\n') if r != '']
n = int(p[0])
s = p[1:]
for i, r in enumerate(s):
    t = list(r)
    t.sort()
    s[i] = ''.join(t)
total = 0
while n:
    a = s.pop(-1)
    count = 0
    for i in reversed(range(0, len(s))):
        if s[i] == a:
            count += 1
            s[i] = None
    total += int((count + 1) * count / 2)
    n -= (count + 1)
print(total)

### FIXED CODE ###

import sys
p = [r for r in sys.stdin.read().split('\n') if r != '']
n = int(p[0])
s = p[1:]
for i, r in enumerate(s):
    t = list(r)
    t.sort()
    s[i] = ''.join(t)
d = {}
for i in s:
    if i in d:
        d[i] += 1
    else:
        d[i] = 0
count = 0
for k, v in d.items():
    count += int((v + 1) * v / 2)
print(count)
import sys
input = sys.stdin.readline
N = int(input())
N_str = list(str(N))
a = 0
for i in N_str:
    cnt += int(i)
if N % a == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
N_str = list(str(N))
a = 0
for i in N_str:
    a += int(i)
if N % a == 0:
    print("Yes")
else:
    print("No")
"""
imos
"""
N, M = map(int,input().split())

from itertools import accumulate
imos = [0]*(N+1)
for i in range(M):
    L,R = map(int,input().split())
    imos[L] += 1
    imos[R+1] -= 1
acc = list(accumulate(imos))
print(sum([1 for a in acc if a == M]))

### FIXED CODE ###

N, M = map(int,input().split())
Ls,Rs = [],[]
for i in range(M):
    L,R = map(int,input().split())
    Ls.append(L)
    Rs.append(R)

print(max(0,min(Rs)-max(Ls)+1))