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

N,K = map(int,input().split())
ary = [0]+list(map(int,input().split()))
dp = [[0]*N for _ in range(N)]
check = [[False]*N for _ in range(N)]
ary = sorted(ary)
a = ary.index(0)
ary.pop(a)
ans = float("Inf")
for i in range(N):
    for j in range(N):
        dp[i][j] = [abs(ary[i]-ary[j]),abs(j-i)]
for i in range(N):
    for j in range(i,N):
        if i <= j <= a-1:continue
        if i == j:
            k = abs(dp[i][i][1] - a)
            d = abs(ary[i])
            if k >= K and ans > d:
                ans = d
            continue

        k = 1 + dp[i][j][1]
        d = abs(ary[i]) + dp[i][j][0]
        if k >= K and ans > d:
            ans = d
print(0 if ans == float("Inf") else ans)

### FIXED CODE ###

N, K = map(int, input().split())
ary = [0] + list(map(int, input().split()))
ary.sort()
zero = ary.index(0)
a = [abs(i - zero) for i in range(N + 1)]
ary.pop(zero)
ans = float("Inf")
for i in range(N - K + 1):
    b = N - i - 1
    d = abs(ary[i])
    if a[i] >= K:
        ans = min(ans, d)
    ans = min(ans, d + abs(ary[i] - ary[i + K - 1]))
    d = abs(ary[b])
    if a[b] >= K:
        ans = min(ans, d)
    ans = min(ans, d + abs(ary[b] - ary[b - K + 1]))
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
B.sort()
C=list(map(int,input().split()))
C.sort()
from bisect import bisect_right
ret=0
Cb=[0]*(N+1)
prebr=0
for i in range(N):
  prebr+=bisect_right(C[prebr:],B[i])
  Cb[i]=N-prebr
for i in range(N-1,-1,-1):
  Cb[i]+=Cb[i+1]
for a in A:
  bi=bisect_right(B,a)
  ret+=Cb[bi]
print(ret)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
B.sort()
C=list(map(int,input().split()))
C.sort()
from bisect import bisect_right
ret=0
Cb=[0]*(N+1)
for i in range(N):
  Cb[i]=N-bisect_right(C,B[i])
for i in range(N-1,-1,-1):
  Cb[i]+=Cb[i+1]
for a in A:
  bi=bisect_right(B,a)
  ret+=Cb[bi]
print(ret)
### BUGGY CODE ###

while True:
    try:
        ary = map(int,raw_input().split())
        c = max(ary)
        ary.remove(c)
        a,b = ary

        if a**2 + b**2 == c**2:
            print "YES"
        else:
            print "NO"
    except:
        continue

### FIXED CODE ###

for i in range(input()):

    ary = map(int,raw_input().split())
    c = max(ary)
    ary.remove(c)
    a,b = ary

    if a**2 + b**2 == c**2:
        print "YES"
    else:
        print "NO"
### BUGGY CODE ###

import queue

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

G = [ [] for i in range( N ) ]
for i in range( M ):
  u, v = map( int, input().split() )
  G[ u - 1 ].append( v - 1 )
  G[ v - 1 ].append( u - 1 )

Q = int( input() )
V = []
D = []
C = []
for qi in range( Q ):
  v, d, c = map( int, input().split() )
  V.append( v - 1 )
  D.append( d )
  C.append( c )

vis = [ -1 for i in range( N ) ]
col = [ 0 for i in range( N ) ]
for qi in range( Q - 1, -1, -1 ):
  if D[ qi ] <= vis[ V[ qi ] ]: continue # 影響力不足
  que = queue.Queue()
  vis[ V[ qi ] ] = D[ qi ]
  que.put( ( D[ qi ], V[ qi ] ) )
  if col[ V[ qi ] ] == 0:
    col[ V[ qi ] ] = C[ qi ]
  while not que.empty():
    d, u = que.get()
    if d == 0: continue
    for v in G[ u ]:
      if vis[ v ] >= d - 1: continue
      vis[ v ] = d - 1
      que.put( ( d - 1, v ) )
      if col[ v ] == 0:
        col[ v ] = C[ qi ]

for i in range( N ):
  print( col[ i ] )


### FIXED CODE ###

from collections import deque

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

G = [ [] for i in range( N ) ]
for i in range( M ):
  u, v = map( int, input().split() )
  G[ u - 1 ].append( v - 1 )
  G[ v - 1 ].append( u - 1 )

Q = int( input() )
V = []
D = []
C = []
for qi in range( Q ):
  v, d, c = map( int, input().split() )
  V.append( v - 1 )
  D.append( d )
  C.append( c )

vis = [ -1 for i in range( N ) ]
col = [ 0 for i in range( N ) ]
for qi in range( Q - 1, -1, -1 ):
  if D[ qi ] <= vis[ V[ qi ] ]: continue # 影響力不足
  que = deque()
  vis[ V[ qi ] ] = D[ qi ]
  que.append( ( D[ qi ], V[ qi ] ) )
  if col[ V[ qi ] ] == 0:
    col[ V[ qi ] ] = C[ qi ]
  while len( que ):
    d, u = que.popleft()
    if d == 0: continue
    for v in G[ u ]:
      if vis[ v ] >= d - 1: continue
      vis[ v ] = d - 1
      que.append( ( d - 1, v ) )
      if col[ v ] == 0:
        col[ v ] = C[ qi ]

for i in range( N ):
  print( col[ i ] )
### BUGGY CODE ###

from collections import Counter

N, P = map(int, input().split())
S = input()

sum = 0
if P == 2 or P == 5:
    for i in range(N):
        if int(S[i]) % P == 0:
            sum += i+1
    print(sum)
    exit()

m = [0] * N
for i in range(N):
    m[i] = int(S[i:]) % P
    
mc = Counter(m)

for v in mc.values():
    if v > 1:
        sum += v*(v-1)//2

sum += mc[0]

print(sum)

### FIXED CODE ###

from collections import Counter

N, P = map(int, input().split())
S = input()

sum = 0
if P == 2 or P == 5:
    for i in range(N):
        if int(S[i]) % P == 0:
            sum += i+1
    print(sum)
    exit()

m = []
t = 1
q = 0
for i in range(N,0,-1):
    q = ((int(S[i-1]) % P) * t + q) % P
    m.append(q)
    t = (10 * t) % P
    
mc = Counter(m)

for v in mc.values():
    if v > 1:
        sum += v*(v-1)//2

sum += mc[0]

print(sum)
### BUGGY CODE ###

n = int(input())
apple = []
for _ in range(n):
    apple.append(int(input()))
for i in range(n):
    orange = apple[0:i] + apple[i+1:n+1]
    print(max(orange))

### FIXED CODE ###

n = int(input())
apple = []
for _ in range(n):
    apple.append(int(input()))
big = max(apple)
orange = [big for i in range(n)]
num = apple.index(big)
del apple[num]
cat = max(apple)
orange[num] = cat
for i in orange:
    print(i)
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()

rlist = []
v = 1
while True:
    r = v % P
    if r in rlist:
        break
    rlist.append(r)
    v *= 10

MAX_N = 2*(10**5)+10
rmap = [[None] * MAX_N for i in range(MAX_N)]

ans = 0
for i in range(len(S)-1, -1, -1):
    for j in range(i, -1, -1):
        r = 0
        dr = rlist[j-i]
        nr = rmap[i+1][j]
        if nr:
            r = dr + nr
        else:
            r = dr
        if r == 0:
            ans += 1
        rmap[i][j] = r
    
print(ans)


### FIXED CODE ###

N, P = map(int, input().split())
S = input()

r_circ = []
v = 1
while True:
    r = v % P
    if r in r_circ:
        break
    r_circ.append(r)
    v *= 10

ans = 0
if P in (2, 5):
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
else:
    pr = 0
    rcntmap = [0] * P
    rcntmap[0] = 1  # r - 0 patten
    for i in reversed(range(len(S))):
        d = int(S[i])
        r = (d * r_circ[(len(S)-1-i) % len(r_circ)] + pr) % P
        #r = int(S[i:]) % P
        ans += rcntmap[r]
    
        rcntmap[r] += 1
        pr = r

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

N = int(input())
num = N

while num % N != 0 or num % 2 != 0:
    num += 1

print(num)

### FIXED CODE ###

N = int(input())

if N % 2:
    print(2*N)
else:
    print(N)
### BUGGY CODE ###

from collections import Counter

def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  Q = int(input())

  countA = Counter(A)

  for _ in range(Q):
    B, C = map(int, input().split(" "))
    if B in countA.keys():
      countA[C] += countA.pop(B)
    sum_A = 0
    for a in countA.items():
      sum_A += a[0]*a[1]
    print(sum_A)

if __name__ == "__main__":
  resolve()


### FIXED CODE ###

from collections import Counter

def resolve():
  N = int(input())
  countA = Counter([int(x) for x in input().split(" ")])
  Q = int(input())

  sum_A = 0
  for a in countA.keys():
    sum_A += a*countA[a]

  for _ in range(Q):
    B, C = map(int, input().split(" "))
    if B in countA.keys():
      target_value = countA.pop(B)
      sum_A += (C - B) * target_value
      countA[C] += target_value
      print(sum_A)
    else:
      print(sum_A)


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

n = int(input())
a = list(map(int, input().split()))
divide_minimam_prime = [i for i in range(max(a) + 1)]
is_prime = [True for i in range(max(a) + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(2,int(max(a)**0.5) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= max(a):
            is_prime[k] = False
            if divide_minimam_prime[k] == k:
                divide_minimam_prime[k] = div
            k += div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(k)
        while k % divide_minimam_prime[k] == 0:
            k = k // divide_minimam_prime[k]
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MAX_A = max(a)
divide_minimam_prime = [i for i in range(MAX_A + 1)]
is_prime = [True for i in range(MAX_A + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(2,int(MAX_A**0.5) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= MAX_A:
            is_prime[k] = False
            if divide_minimam_prime[k] == k:
                divide_minimam_prime[k] = div
            k += div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(divide_minimam_prime[k])
        div = divide_minimam_prime[k]
        while k % div == 0 and k > 1:
            k = k // div
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

import pdb


def main():
    num = int(input())
    array = []
    tmp = input()
    for i in range(num):
        array.append(int(tmp.split()[i]))
        
    ans = 1
    div = 0
    prev = 0
    count = 0
    #pdb.set_trace()
    for tmp in array:
        if(count == 0):
            prev = tmp
            count += 1
            continue

        if div == 0:
            if prev < tmp:
                div = 1
            elif prev > tmp:
                div = -1

        if prev < tmp and div == -1:
            ans += 1
            div = 0
        elif prev > tmp and div == 1:
            ans += 1
            div = 0

        prev = tmp
        
    print(ans)

        
if __name__ == '__main__':
    main()


### FIXED CODE ###

import pdb


def main():
    num = int(input())
    array = []
    tmp = input()
    tmp = tmp.split()
    for i in range(num):
        array.append(int(tmp[i]))
        
    ans = 1
    div = 0
    prev = 0
    count = 0
    #pdb.set_trace()
    for tmp in array:
        count += 1
        if count == 1:
            prev = tmp
            continue

        if div == 0:
            if prev < tmp:
                div = 1
            elif prev > tmp:
                div = -1
        else:
            if prev < tmp and div == -1:
                ans += 1
                div = 0
            elif prev > tmp and div == 1:
                ans += 1
                div = 0
                
        prev = tmp
        
    print(ans)

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

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

def choose(n, r, mod = 10 ** 9 + 7):
    bumbo = 1
    bunshi = 1
    for i in range(r):
        bumbo *= (n - i)
        bunshi *= (i + 1)
    return [bumbo%mod, bunshi%mod]

mod = 10 ** 9 + 7
n, a, b = map(int, input().split())

ans = pow(2, n, mod)    # 全体
ans -= 1    # 花を選ばない場合をひく

# nCa を求める
a1, a2 = choose(n, a)
nCa = a1 * pow(a2, mod-2, mod)

b1, b2 = choose(n, b)
nCb = b1 * pow(b2, mod-2, mod)


ans -= (nCa + mod) % mod
ans -= (nCb + mod) % mod
print(ans)

### FIXED CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def comb(n, r, p):
    ret = 1
    while 1:
        if (r == 0):
            break
        N = n % p
        R = r % p
        if N < R:
            return 0
        for i in range(R):
            ret = ret * (N-i) % p
        imul = 1
        for i in range(R):
            imul = imul * (i+1) % p
        ret = ret * modinv(imul, p) % p
        n //= p
        r //= p
    return ret

mod = 10 ** 9 + 7
N, A, B = map(int, input().split())
tmp = (2 ** N - 1) % mod 
a = comb(N, A, mod)
b = comb(N, B, mod)
print(((tmp + mod) - a - b ) % mod)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Feb 24 16:22:35 2019
 
@author: Owner
"""
 
N, K = map(int, input().split())
 
h = list(map(int, input().split()))
 
dp = []
 
for n in range(N):
    if n == 0:
        dp.append(0)
    else:
        temp = float("inf")
        for k in range(1,K+1):
            if n-k >= 0:
                temp = min(temp, dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
        dp.append(temp)
    #print(dp)
print(dp[N-1])

### FIXED CODE ###

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

import numpy as np

N, K = map(int, input().split())
 
h = np.array(list(map(int, input().split())))
 
dp = np.zeros(N)
 
for n in range(1, N):
    k = min(K, n)
    temp = np.min(dp[n-k:n] + np.abs(h[n]-h[n-k:n]))
    dp[n] = temp
print(int(dp[-1]))
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
nums = [0]*N

for i in range(N):
  nums[A[i]-1] += 1

nums.sort()

while True:
  if nums[0] == 0:
    del nums[0]
  else:
    break

if len(nums) <= K:
  print(0)
else:
  print(sum(nums[:len(nums)-K]))

### FIXED CODE ###

from collections import deque

N,K = map(int,input().split())
A = list(map(int,input().split()))
nums = [0]*N

for i in range(N):
  nums[A[i]-1] += 1

nums.sort()

nums = deque(nums)

while True:
  if nums[0] == 0:
    nums.popleft()
  else:
    break
nums = list(nums)
if len(nums) <= K:
  print(0)
else:
  print(sum(nums[:len(nums)-K]))
### BUGGY CODE ###

import sys
import os
import math
import itertools

def factorize(n):
    b = 2
    fct = []
    fct.append(1)
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

N = int(input())
listN = factorize(N)
x = 0
y = 0
L = [True for i in range(N*N)]
mini = 10**12
if len(listN) == 1:
    x = N
    y = 1
else:
    for i in range(1,len(listN)):
        tmp = list(itertools.combinations(listN,i))
        for j in range(len(tmp)):
            x0,y0 = 1,1
            for k in range(len(tmp[j])):
                x0 *= tmp[j][k]
                if L[x0]:
                    y0 = N//x0
                    if mini > abs(x0+y0):
                        mini = abs(x0+y0)
                        x = x0
                        y = y0
                        L[x0] = False
print(x-1+y-1)


### FIXED CODE ###

import sys
import os

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

N = int(input())
listN = make_divisors(N)
mini = 10**12
if len(listN) == 1:
    x = N
    y = 1
else:
    for i in range(len(listN)):
        x = listN[i]
        y = N//x
        mini = min(x+y,mini)
print(x-1+y-1)
### BUGGY CODE ###

# cook your dish here
n = int(input())
a = list(map(int,input().split()))
b = []

for i in range(n):
    if i % 2 == 0:
        b = [a[i]]+b
    else:
        b.append(a[i])
c = b[::-1]
ass = ''
for i in range(n):
    if n %2 == 0:
        ass += str(c[i]) + ' '
    else:
        ass += str(b[i]) + ' '
print(ass)

    

### FIXED CODE ###

# cook your dish here
n = int(input())
a = list(map(int,input().split()))
c = []
d = []

for i in range(n):
    if i %2 == 0:
        c.append(a[i])
    else:
        d.append(a[i])
c = c[::-1]

b = c + d
c = b[::-1]
ass = ''
for i in range(n):
    if n %2 == 0:
        ass += str(c[i]) + ' '
    else:
        ass += str(b[i]) + ' '
print(ass)
### BUGGY CODE ###

N = int(input())
S = list(map(str, input().split()))
A = 0
for i in range(N):
    for j in range(N-1):
        for k in range(N-2):
            for l in range(N-3):
                if S[i] != S[j+1] and S[j+1] != S[k+2]and S[k+2] != S[l+3] and S[l+3] != S[i] and S[j+1] != S[l+3] and S[i] != S[k+2]:
                    A = A+1
if A != 0:
    print("Four")
else:
    print("Three")


### FIXED CODE ###

N = int(input())
S = list(map(str, input().split()))
if ("P"and "W" and "G" and "Y") in S:
    print("Four")
else:
    print("Three")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#a, b = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mod = (10 ** 9) + 7


def lcm(a):
  from fractions import gcd
  x = a[0]
  for i in range(1, len(a)):
      x = (x * a[i]) // gcd(x, a[i])
  return x

p = lcm(A)
#print (p)

sum = 0
for i in range(N) :
  sum += p//A[i]

print (int(sum%mod))



### FIXED CODE ###

# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#a, b = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mod = (10 ** 9) + 7


def lcm(a):
  from fractions import gcd
  x = a[0]
  for i in range(1, len(a)):
      x = (x * a[i]) // gcd(x, a[i])
  return x

p = lcm(A)
#print (p)

sum = 0
for i in range(N) :
  sum += p//A[i]

print (int(sum%mod))
### BUGGY CODE ###

#!/usr/bin/env python3

import numpy as np


def solve(H, W, S):
    grid = np.zeros(H*W, dtype=np.int)
    for y in range(H):
        count = 0
        start = 0
        yw = y * W
        for x in range(W):
            if S[y][x] == '#':
                grid[yw+start:yw+x] = count
                start = x + 1
                count = 0
            else:
                count += 1
        grid[yw+start:yw+W] = count

    for x in range(W):
        count = 0
        start = 0
        for y in range(H):
            if S[y][x] == '#':
                grid[(start*W+x):(y*W+x):W] += count
                start = y + 1
                count = 0
            else:
                count += 1

        grid[(start*W+x):(H*W+1):W] += count

    return grid.max() - 1


if __name__ == '__main__':
    H, W = map(int, input().split())
    S = [input().strip() for _ in range(H)]

    ans = solve(H, W, S)

    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3


def solve(H, W, S):
    grid = [[0] * W for _ in range(H)]
    for y in range(H):
        count = 0
        start = 0
        for x in range(W):
            if S[y][x] == '#':
                for i in range(start, x):
                    grid[y][i] = count
                start = x + 1
                count = 0
            else:
                count += 1
        for i in range(start, W):
            grid[y][i] = count

    for x in range(W):
        count = 0
        start = 0
        for y in range(H):
            if S[y][x] == '#':
                for i in range(start, y):
                    grid[i][x] += count
                start = y + 1
                count = 0
            else:
                count += 1
        for i in range(start, H):
            grid[i][x] += count

    ans = 0
    for x in range(W):
        for y in range(H):
            if grid[y][x] > ans:
                ans = grid[y][x]
    return ans - 1


if __name__ == '__main__':
    H, W = map(int, input().split())
    S = [input().strip() for _ in range(H)]

    ans = solve(H, W, S)

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

from collections import Counter
import numpy as np

n, m = map(int, input().split())
tar = [0] * (1 + 10 ** 5)
tar = np.array(tar)

for i in range(m):
    l, r = map(int, input().split())
    tar[l:r + 1] += 1
    #print(tar[:10])

#tar = tar.tolist()
# print(tar[0:5])
count = Counter(tar)
ans = count[m]
print(ans)
'''
n, m = map(int, input().split())

ll, rr = map(int, input().split())
for i in range(m - 1):
    l, r = map(int, input().split())

    #lについて
    if (l <= ll):
      pass
    elif (ll < l )

ans = max(ll - rr, 0)
print(ans)

'''


### FIXED CODE ###

from collections import Counter
import numpy as np

n, m = map(int, input().split())
data = [0] * m

for i in range(m):
    data[i] = list(map(int, input().split()))


data = np.array(data)
ll = data[:, 0]
rr = data[:, 1]

ans = np.min(rr) - max(ll) + 1
ans = max(0, ans)
print(ans)

'''
n, m = map(int, input().split())
tar = [0] * (1 + 10 ** 5)
tar = np.array(tar)

for i in range(m):
    l, r = map(int, input().split())
    tar[l:r + 1] += 1
    #print(tar[:10])

#tar = tar.tolist()
# print(tar[0:5])
count = Counter(tar)
ans = count[m]
print(ans)
#-----------------------------
n, m = map(int, input().split())

ll, rr = map(int, input().split())
for i in range(m - 1):
    l, r = map(int, input().split())

    #lについて
    if (l <= ll):
      pass
    elif (ll < l )

ans = max(ll - rr, 0)
print(ans)

'''