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

N = int(input())
A = [int(i) for i in input().split(' ')]

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

divisors_list = {}
for i in A:
  divisors_list[i] = []

for k,i in enumerate(A):
  for j in make_divisors(i):
    try:
      divisors_list[j].append(k)
    except:
      continue

pass_li = {}
for i in range(N):
  pass_li[i] = 1

for i in range(N):
  tmp = pass_li[i]
  for j in divisors_list[A[i]]:
    pass_li[j] = 0
  pass_li[i] = tmp 
  
  
print(sum(pass_li.values()))




  
  


### FIXED CODE ###

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

MAX_A = 1000001

dp = [0]*MAX_A

for i in A:
  if dp[i] == 0:
    for j in range(i, MAX_A,i):
      dp[j] += 1
  else:
    dp[i] += 1

c = 0
for i in A:
  if dp[i] == 1:
    c += 1

print(c)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
nowmin = a[0] + 1
ans = a[1]-a[0]
for i in range(n-1):
  if a[i] < nowmin:
    k = max(a[i+1:]) - a[i]
    if k > ans:
      ans =  k
      nowmin = a[i]
    
print(ans)



### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
nowmin = a[0]
nowmax = max(a[1:])
ans = nowmax - nowmin
for i in range(n-1):
  if a[i] == nowmax:
    nowmax = max(a[i+1:])
  if a[i] < nowmin:
    k = nowmax - a[i]
    if k > ans:
      ans =  k
      nowmin = a[i]


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

import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int(input())
    a = list(map(int, input().split()))
    A = deque(sorted(a))
    B = deque([])
    ans = []
    S = True
    while True:
        if len(A) == 0:
            break
        rem = []
        L = A.popleft()
        for i in A:
            if i == L:
                S = False
            if i%L == 0:
                rem.append(i)
        for r in rem:
            A.remove(r)
        if S:
            ans.append(L)
        S = True
    print(len(ans))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int(input())
    a = list(map(int, input().split()))
    arr = [0]*(10**6 + 1)
    for x in a:
        if arr[x] == 0:
            for i in range(x, 10**6 + 1, x):
                arr[i] += 1
        else:
            arr[x] += 1
    ans = 0
    for i in a:
        if arr[i] == 1:
            ans += 1
    print(ans)
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np
a,b,q = map(int,input().split())
s = np.array([-np.inf]+[int(input()) for i in range(a)]+[np.inf])
t = np.array([-np.inf]+[int(input()) for i in range(b)]+[np.inf])
x = np.array([int(input()) for i in range(q)])

def distance(s,t,xi):
  s_ = s-xi
  s_m = s_[s_<=0].max()
  s_p = s_[s_>=0].min()
  t_ = t-xi
  t_m = t_[t_<=0].max()
  t_p = t_[t_>=0].min()
  
  return min(abs(min(s_m,t_m)),abs(t_p-s_m)+min(abs(t_p),abs(s_m))\
         ,abs(max(t_p,s_p)),abs(s_p-t_m)+min(abs(s_p),abs(s_p)))
 
for i in x:
  print(int(distance(s,t,i)))

### FIXED CODE ###

import numpy as np
import bisect
a,b,q = map(int,input().split())
s = np.array([-np.inf]+[int(input()) for i in range(a)]+[np.inf])
t = np.array([-np.inf]+[int(input()) for i in range(b)]+[np.inf])
x = np.array([int(input()) for i in range(q)])


  
def distance(s,t,xi):
  s_ = bisect.bisect_left(s,xi)
  s_m = abs(s[s_-1]-xi)
  s_p = abs(s[s_]-xi)
  t_ = bisect.bisect_left(t,xi)
  t_m = abs(t[t_-1]-xi)
  t_p = abs(t[t_]-xi)
  
  return min(max(s_m,t_m),s_m+t_p+min(s_m,t_p),s_p+t_m+min(s_p,t_m),max(s_p,t_p))
 
for i in x:
  print(int(distance(s,t,i)))
### BUGGY CODE ###

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

ans = 1
for i in A_list:
    ans *= i

if 10 ** 18 < ans:
    print('-1')
else:
    print(ans)




### FIXED CODE ###

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

    if 0 in set(A_list):
        print(0)
        exit()

    ans = 1
    for i in A_list:
        ans *= i
        if 1000000000000000000 < ans:
            print('-1')
            exit()
    else:
        print(ans)


main()
### BUGGY CODE ###


n = int(input())
power = 1

for i in range(1,n+1):
    power *= i

#print(power)
print(power % (10**9 + 7))


### FIXED CODE ###


n = int(input())
ans = 1

for i in range(1,n+1):
    ans *= i
    ans = ans % (10**9 + 7)

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

import operator as op
from functools import reduce
 
def npr(n, r):
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    return numer


N, K = list(map(int, input().split()))
q = 1000000007

# edge_mat[i][j] = 1 iff vertex_i and vertex_j are connected
edge_mat = [[0 for j in range(N)] for i in range(N)]
for k in range(N - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    edge_mat[a][b] = 1
    edge_mat[b][a] = 1

# ナンバリングは０オリジン
# 頂点０をrootとする

# depth1 = 階層１の頂点を列挙
depth1 = []
for j in range(1, N):
    if edge_mat[0][j] == 1:
        depth1.append(j)

# 各頂点から出る子の個数を列挙
child_num = [0 for i in range(N)]
child_num[0] = len(depth1)
for j in range(1, N):
    child_num[j] = sum(edge_mat[j]) - 1

# calculate
min_child = min(child_num)
if K < min_child:
    print(0)
else:
    ans = (K * npr(K - 1, child_num[0])) % q
    for i in range(1, N):
        val = npr(K - 2, child_num[i]) % q
        ans = (ans * val) % q
    print(ans)

### FIXED CODE ###

import operator as op
from functools import reduce
 
def npr(n, r):
    numer = 1
    for k in range(r):
        numer = numer * (n - k)
        numer %= q
    return numer


N, K = list(map(int, input().split()))
q = 1000000007

child_num = [0 for i in range(N)]
for k in range(N - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    child_num[a] += 1
    child_num[b] += 1

for i in range(1, N):
    child_num[i] -= 1

# calculate
min_child = min(child_num)
if K < min_child:
    print(0)
else:
    ans = (K * npr(K - 1, child_num[0])) % q
    for i in range(1, N):
        val = npr(K - 2, child_num[i]) % q
        ans = (ans * val) % q
    print(ans)
### BUGGY CODE ###

if __name__ == "__main__":

    N = int(input())

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

    mult = 1
    for i in P:
        mult *= i

    A = 10 ** 18
    if(mult > A):
        print(-1)
    else:
        print(mult)



### FIXED CODE ###

import sys

if __name__ == "__main__":
 
    N = int(input())
 
    P = list(map(int,input().split()))

    if(0 in P):
        print(0)
    else:
        P.sort()

        mult = 1
        for i in P:
            mult *= i 
            if (mult > 10 ** 18):
                print(-1)
                sys.exit()

        print(mult)
### BUGGY CODE ###

import math
  
def divisors(n):
  count = 0
  i = 1
  max = math.sqrt(n)
  while i <= max:
    if n % i == 0 and i < max:
      count += 2
    elif n % i == 0 and i == max:
      count += 1
    i += 1
  return count

N = int(input())
ans = 0

for i in range(N):
  j = i+1
  ans += j * divisors(j)
  
print(ans)
  


### FIXED CODE ###

N = int(input())
ans = 0
 
for i in range(1, N+1):
  Y = N // i
  ans += Y * (Y+1) * i / 2
  
print(int(ans))
### BUGGY CODE ###

n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for _ in range(q)]
all_a=[]
def make_a(t):
  if len(t)==n:
    return [t]
  ret=[]
  for ti in range(t[-1],m+1):
    ret.extend(make_a(t+[ti]))
  return ret
for i in range(1,m+1):
  all_a.extend(make_a([1]))
ans=0
for an in all_a:
  ansi=0
  for a,b,c,d in abcd:
    if an[b-1]-an[a-1]==c:
      ansi+=d
  ans=max(ans,ansi)
print(ans)

### FIXED CODE ###

n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for _ in range(q)]
# dfsで数列を生成
def dfs():
  todo=[[]]
  ret=[]
  while len(todo)>0:
    t=todo.pop()
    if len(t)==n:
      ret.append(t)
    else:
      l=t[-1] if len(t)>0 else 1
      for i in range(l,m+1):
        tc=t.copy()
        tc.append(i)
        todo.append(tc)
  return ret
def point(s):# 数列sに対する特典
  ret=0
  for a,b,c,d in abcd:
    if s[b-1]-s[a-1]==c:
      ret+=d
  return ret
a=dfs()
ans=0
for ai in a:
  ans=max(ans,point(ai))
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
cnt = 0
for i in range(n-k+1):
    cnt = max(cnt, sum(p[i:i+k]))
print((cnt+k)/2)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
p = list(map(int, input().split()))
cnt = sum(p[0:k])
tmp = 0
for i in range(k, n):
    if p[i] + tmp - p[i-k] > 0:
        cnt += p[i]-p[i-k]+tmp
        tmp = 0
    else:
        tmp += p[i]-p[i-k]
print((cnt+k)/2)
### BUGGY CODE ###

from collections import Counter
 
input()
c = Counter(map(int, input().split()))
r = int(c[1] == 1)
if c[1] == 0:
  for k, v in c.items():
    if v == 1:
      i = 2
      while i * i <= k and (k % i or i not in c and k // i not in c):
        i += 1
      if i * i > k:
        r += 1
print(r)


### FIXED CODE ###

N = 1000001
a = [0]* N
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  for j in range(i + i, N, i):
    if a[i]:
      a[j] = 0
print(a.count(1))
### BUGGY CODE ###

#coding:UTF-8
def NI(A):
    cnt=0
    for i in range(len(A)):
        for j in reversed(range(i+1,len(A))):
            if A[j]<A[j-1]:
                swap=A[j]
                A[j]=A[j-1]
                A[j-1]=swap
                cnt+=1
    print(cnt)
    
if __name__=="__main__":
    n=int(input())
    A=input().split(" ")
    for i in range(n):
        A[i]=int(A[i])
    NI(A)

### FIXED CODE ###

 #coding:UTF-8
def Marge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    L=[]
    R=[]
    c=0
    for i in range(n1):
        L.append(A[left+i])
    for i in range(n2):
        R.append(A[mid+i])
    L.append(100000000000000000)
    R.append(100000000000000000)
    i=j=0
    for k in range(left,right):
        if L[i]<=R[j]:
            A[k]=L[i]
            i+=1
        else:
            A[k]=R[j]
            j+=1
            c+=n1-i
    return c
            
def MS(A,left,right,c):
    
    if left+1<right:
        mid=int((left+right)/2)
        c1=MS(A,left,mid,c)
        c2=MS(A,mid,right,c)
        c3=Marge(A,left,mid,right)
        return c1+c2+c3
    return 0
 
    
if __name__=="__main__":
    n=int(input())
    A=input().split(" ")
    cnt=0
    for i in range(n):
        A[i]=int(A[i])
    cnt=MS(A,0,n,0)
    print(cnt)
### BUGGY CODE ###

from itertools import accumulate

def equalfind(A):#配列中の等しい要素の組をカウント　オーダーはO(NlogN)
    A.sort()
    s=1
    count=0
    if len(A)==1:
        return count
    else:
        for i in range(0,len(A)-1):
            if A[i]==A[i+1]:
                s+=1
            else:
                count+=s*(s-1)//2
                s=1
        return count+s*(s-1)//2


N,P=map(int,input().split())
S=input()
if P!=2 and P!=5:
    data=[(int(S[i])*(10**(N-i-1)))%P for i in range(0,N)]
    ans=list(accumulate(data))
    ans=[ans[i]%P for i in range(0,N)]
    ans.append(0)
    print(equalfind(ans))
elif P==2:
    ans=0
    for i in range(0,N):
        if int(S[i])%2==0:
            ans+=i+1
    print(ans)
else:
    ans=0
    for i in range(0,N):
        if int(S[i])%5==0:
            ans+=i+1
    print(ans)


### FIXED CODE ###

from itertools import accumulate

def equalfind(A):#配列中の等しい要素の組をカウント　オーダーはO(NlogN)
    A.sort()
    s=1
    count=0
    if len(A)==1:
        return count
    else:
        for i in range(0,len(A)-1):
            if A[i]==A[i+1]:
                s+=1
            else:
                count+=s*(s-1)//2
                s=1
        return count+s*(s-1)//2

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

def pow(x, n):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = (ans*x)%P
    x = (x*x)%P
    n = n >> 1 #ビットシフト
  return ans%P

if P!=2 and P!=5:
    data=[(int(S[i])*(pow(10,N-1-i)))%P for i in range(0,N)]
    ans=list(accumulate(data))
    ans=[ans[i]%P for i in range(0,N)]
    ans.append(0)
    print(equalfind(ans))
elif P==2:
    ans=0
    for i in range(0,N):
        if int(S[i])%2==0:
            ans+=i+1
    print(ans)
else:
    ans=0
    for i in range(0,N):
        if int(S[i])%5==0:
            ans+=i+1
    print(ans)
### BUGGY CODE ###

import copy

def main():
    n = int(input())
    a = list( map( int, input().split()))
    sum = 1
    for i in a:
        k = copy.deepcopy(sum)
        sum = k * i
    if sum - 1000000000000000000 > 0:
        print(-1)
    else:
       print(sum)
    
if __name__ == '__main__':
    main()
   

### FIXED CODE ###

import copy

def main():
    n = int(input())
    a = list( map( int, input().split()))
    sum = 1
    if 0 in a:
        print(0)
    else:
        for i in a:
            sum = sum * i
            if sum > 1000000000000000000:
                print(-1)
                exit()
        print(sum)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
AC = [0] * N

for i in range(len(S)-1):
    if S[i] == 'A' and S[i+1] == 'C':
        AC[i] = 1

for i in range(Q):
    start, end = map(lambda x:int(x)-1, input().split())
    ans = sum(AC[start:end+1])
    if AC[end] == 1 and ans != 0:
        ans -= 1
    print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
AC = [0] * N

for i in range(1, len(S)):
    if S[i-1] == 'A' and S[i] == 'C':
        AC[i] = AC[i-1] + 1
    else:
        AC[i] = AC[i-1]


for i in range(Q):
    start, end = map(lambda x:int(x)-1, input().split())
    print(AC[end] - AC[start])
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
a = [int(c) for c in input().split()]
MOD = 10**9+7
dic = defaultdict(int)
ls = defaultdict(int)
for i in range(N):
  c = a[i]
  for j in range(2, int(c**0.5)+1):
    if c%j==0:
      cnt = 0
      while c%j==0:
        c //= j
        cnt += 1
      ls[(i,j)] = cnt
      dic[j] = max(dic[j], cnt)
  if c!=1:
    ls[(i,c)] = 1
    dic[c] = max(dic[c], 1)
ans = 0
for i in range(N):
  b = 1
  for k in dic.keys():
    x = int(k)
    b *= k**(dic[k]-ls[(i,k)])
    b %= MOD
  ans += b
  ans %= MOD
print(ans)


### FIXED CODE ###

import numpy as np
N = int(input())
a = np.array(input().split(), np.int64)
MOD = 10**9+7
U = 10**6+10
is_prime = np.zeros(U, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3, U, 2):
  if p*p>U:
    break
  if is_prime[p]==1:
    is_prime[p*p::p+p] = 0

M = 10**3
small_primes = np.where(is_prime[:M])[0].tolist()

B = a.copy()
lcm = 1
for p in small_primes:
  e = 0
  while np.any(a%p==0):
    a[a%p==0] //= p
    e += 1
  lcm *= p**e
  lcm %= MOD

for x in set(a.tolist()):
  lcm *= x
  lcm %= MOD

answer = sum(pow(x, MOD-2, MOD) for x in B.tolist())%MOD
answer *= lcm
answer %= MOD
print(answer)
### BUGGY CODE ###

from decimal import Decimal

def main():
    N = int(input())
    A = [Decimal(input()) for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(i+1,N):
            tmp = '{:.20f}'.format(A[i] * A[j])
            if not '.' in tmp:
                cnt += 1
            else:
                a = tmp.split('.')[1]
                if len(a) == a.count('0'):
                    cnt += 1

    print(cnt)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter
from decimal import Decimal

def func(n):
    cnt2 = 0
    cnt5 = 0
    while n % 2 == 0:
        n //= 2
        cnt2 += 1
    while n % 5 == 0:
        n //= 5
        cnt5 += 1
    return cnt2, cnt5

def main():
    N = int(input())
    A = [input() for _ in range(N)]
    ctr = Counter()

    for a in A:
        d = Decimal(a)
        d = int(d * 1000000000)
        cnt2, cnt5 = func(d)
        ctr[(cnt2,cnt5)] += 1
    ans = 0
    for (ni1, go1), v1 in ctr.items():
        for (ni2, go2), v2 in ctr.items():
            if not (ni1 + ni2 >= 18 and go1 + go2 >= 18):
                continue
            if ni1 == ni2 and go1 == go2:
                ans += v1 * (v1 - 1)
            else:
                ans += v1 * v2


    print(ans // 2)


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

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

def find_negative_loop(s,n,w,es):
  # s: start
  # n: number of nodes
  # w: number of edges
  # es[i]: from, to, cost
  
  # d: shortest dist of s -> i
  d = [float('inf')]*n
  d[s] = 0
  for i in range(2*n):
    for j in range(w):
      p, q, r = es[j]
      if d[p] != float('inf') and (d[q] > d[p] + r):
        d[q] = d[p] + r
        if i >= n:
          d[q] = -float('inf')
    if i == n-1:
      temp = d[-1]
  return temp, d[-1]
         

n, w, p = map(int, input().split())
es = []
for i in range(w):
  x, y, z = map(int, input().split())
  es.append([x-1, y-1, (z-p)*(-1)])
  
temp, d = find_negative_loop(0, n, w ,es)
if temp == d:
  print(min(0, d)*(-1))
else:
  print('-1')

### FIXED CODE ###

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

def find_negative_loop(s,n,w,es):
  # s: start
  # n: number of nodes
  # w: number of edges
  # es[i]: from, to, cost
  
  # d: shortest dist of s -> i
  inf = float('inf')
  d = [inf for _ in range(n)]
  d[s] = 0
  for i in range(2*n):
    for j in range(w):
      p, q, r = es[j]
      if d[p] != inf and (d[q] > d[p] + r):
        d[q] = d[p] + r
        if i >= n:
          d[q] = (-1)*inf
    if i == n-1:
      temp = d[-1]
  return temp, d[-1]
         

n, w, p = map(int, input().split())
es = []
for i in range(w):
  x, y, z = map(int, input().split())
  es.append([x-1, y-1, (z-p)*(-1)])
  
temp, d = find_negative_loop(0, n, w ,es)
if temp == d:
  print(min(0, d)*(-1))
else:
  print('-1')
### BUGGY CODE ###

N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        j = i % ki
        if i >= ki :
            if S[i-ki] == 'D' :
                d -= 1
                dm -= m
            elif S[i-ki] == 'M' :
                m -= 1

        if S[i] == 'D' :
            d += 1
        elif S[i] == 'M' :
            m += 1
            dm += d
        elif S[i] == 'C' :
            ret += dm
            
    print(ret)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)
### BUGGY CODE ###

def search(a,x):
    n=len(a)
    for i in range(n):
        if a[n-i-1]==x:
            return a[n-i:n]
    return False

n=int(input())
a=input().split()
min1=n
for i in range(n):
    a[i]=int(a[i])
for i in range(1,n+1):
    a=search(a,i)
    if a==False and i!=1:
        print(n-i+1)
        break
    elif a==False:
        print(-1)
        break
if a!=False:
    print(0)

### FIXED CODE ###

n=int(input())
a=input().split()
j=1
for i in range(n):
    a[i]=int(a[i])
    if a[i]==j:
        j+=1
if n-j+1==n:
    print(-1)
else:
    print(n-j+1)
### BUGGY CODE ###

R, C, K = map(int, input().split())

mesh = [[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    mesh[r][c] = v

# print(*mesh,sep='\n',end='\n\n')

def big3(d): return sorted(d, reverse=True)[:3]

dp = [[0]*(C+1) for _ in range(R+1)]

for i in range(1, R+1):
    for j in range(1, C+1):
        b3 = []
        for k in range(j, C+1):
            b3 = big3(b3 + [mesh[i][k]])
            # print('{} [{}:{}] b3 {} s3 {}'.format(i,j,k,b3,sum(b3)))
            dp[i][k] = max(\
                dp[i][k],\
                dp[i-1][j] + sum(b3),\
                dp[i-1][k] + mesh[i][k]\
                )
        # print('-----')
    # print('{} ['.format(i), end='')
    # for x in dp[i]: print('{:>2} '.format(x),end='')
    # print(']')
# print('===')
print(dp[R][C])


### FIXED CODE ###

R, C, K = map(int, input().split())

V = [[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    V[r][c] = v

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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

from collections import defaultdict


N,K = two_int()

query = []
for i in range(N):
    query.append(two_int() )

query = sorted(query, key=lambda x: x[0])

dicts = defaultdict(int)
count = 0
sums = 0

for [a,b] in query:
    temp = 0
    
    for k,v in dicts.items():
        if k>a:
            dicts[k] += b
        if temp <= k <= a:
            temp = k
            
    dicts[a] = b+dicts[temp]
    sums += b
    if sums > K:
        break

output = [ [k,v] for k,v in dicts.items()]

temp = sorted(output, key=lambda x: x[0])

ans=0
for i in range(len(temp)-1):
    if temp[i][1] < K <= temp[i+1][1]:
        ans=temp[i+1][0]
        break

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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

from collections import defaultdict


N,K = two_int()


query = []
for i in range(N):
    query.append(two_int() )

query = sorted(query, key=lambda x: x[0])

ans=0
sums=0
for q in query:
    if sums < K <= sums+q[1]:
        ans=q[0]
        break
    
    sums += q[1]

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

from bisect import bisect_left
from collections import deque

n = int(input())
ans = []
ans.append(int(input()))

for i in range(n-1):
  
  temp = int(input())
  #print("ans " +  str(ans) + " temp " + str(temp))
  if temp <= ans[0]:
    d = deque(ans)
    d.appendleft(temp)
    ans = list(d)
  else:
    loc = bisect_left(ans, temp)
    ans[loc-1]=temp
#print(ans)
print(len(ans))
  

### FIXED CODE ###

from bisect import bisect_left
from collections import deque

n = int(input())
ans = []
ans.append(int(input()))
ans = deque(ans)
for i in range(n-1):  
  temp = int(input())
  #print("ans " +  str(ans) + " temp " + str(temp))
  if temp <= ans[0]:
    #d = deque(ans)
    #d.appendleft(temp)
    #ans = list(d)
    ans.appendleft(temp)
  else:
    ans[bisect_left(ans, temp)-1]=temp
#print(ans)
print(len(ans))
### BUGGY CODE ###

import numpy as np
N = int(input())
P = list(map(int, input().split()))
cnt = 0
nl = np.array(P)
for i in range(N):
  if np.all(nl[:i+1] >= P[i]):
    cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 0
mi = P[0]
for i in range(N):
	if P[i] <= mi:
		mi = P[i]
		cnt += 1
print(cnt)
### BUGGY CODE ###

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

seki = set(list(range(1,N+1)))
for i in range(M):
    l, r = map(int, input().split())
    seki &= set(list(range(l, r+1)))
print(len(seki))

### FIXED CODE ###

# 解説を見ての解答
from sys import stdin

n, m = map(int, stdin.readline().rstrip().split())
lr = [list(map(int, stdin.readline().rstrip().split())) for i in range(m)]

l, r = lr[0][0], lr[0][1]
for i in range(m):
    l = max(l, lr[i][0])
    r = min(r, lr[i][1])

print(max(0,r-l+1))