Harryxun/stf_run huggingface dataset:
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
bc = [[int(i) for i in input().split()] for i in range(m)]
a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
d = []
cnt1 = 0
cnt2 = 0
x = 0

for lst in bc:
    cnt2 = 0
    while cnt1 < n and cnt2 < lst[0]:
        d.append(lst[1])
        cnt1 += 1
        cnt2 += 1

for i in range(n):
    if d[i] - a[i] < 0:
        x = i
        break

print(sum(d[:x]+a[x:]))

### FIXED CODE ###

n,m = map(int,input().split())
a = [int(i) for i in input().split()]
bc = [[int(i) for i in input().split()] for i in range(m)]
ans = 0
cnt = 0
d = {}

for i in range(n): 
    d[a[i]] = d.get(a[i],0)+1
for k in d: 
    bc.append([d[k],k])
bc.sort(key= lambda x:x[1],reverse=True)

for i in range(len(bc)):
    if cnt < n:
        ans += bc[i][1]*bc[i][0]
        cnt += bc[i][0]
    else:
        ans -= (cnt-n)*bc[i-1][1]
        break
else:
    ans -= (cnt-n)*bc[i][1]

print(ans)
if S[1]!= S[2] and S[1]!=S[3]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S = input()
if S == "AAA" or S == "BBB":
    print("No")
else:
    print("Yes")
import sys
sys.setrecursionlimit(100**6)

def dfs(v, p, g, color, c = 0):
	color[v] = c
	for nv in g[v]:
		if nv[0] == p:
			continue
		nc = c if nv[1] % 2 == 0 else 1 - c
		dfs(nv[0], v, g, color, nc)

def resolve():
	n = int(input())
	color = [-1]*n
	g = [[] for _ in range(n)]
	for i in range(n-1):
		u, v, w = map(int, input().split())
		g[u-1].append([v-1, w])
		g[v-1].append([u-1, w])
	dfs(0, -1, g, color)
	for i in color:
		print(i)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(100**4)

class Edge():
	def __init__(self, v, w):
		self._v = v
		self._w = w
	def v(self):
		return self._v
	def w(self):
		return self._w

def dfs(v, g, colors, color = 0):
	colors[v] = color
	if not len(g[v]):
		return
	for nv in g[v]:
		if colors[nv.v()] != -1:
			continue
		nc = color if nv.w() % 2 == 0 else 1 - color
		dfs(nv.v(), g, colors, nc)

def resolve():
	n = int(input())
	colors = [-1]*n
	g = [list() for _ in range(n)]
	for _ in range(n-1):
		u, v, w = map(int, input().split())
		g[v-1].append(Edge(u-1, w))
		g[u-1].append(Edge(v-1, w))
	for i in range(n):
		if colors[i] != -1:
			continue
		dfs(i, g, colors)
	for c in colors:
		print(c)
resolve()
pen = list(map(str,input().split()))

print(len(collections.Counter(pen)))



### FIXED CODE ###

import collections

pen = list(map(str,input().split()))

print(len(collections.Counter(pen)))
import math

n, q = map(int, input().split(" "))
abL = [list(map(int, input().split(" "))) for _ in range(n - 1)]
pxL = [list(map(int, input().split(" "))) for _ in range(q)]

to = [[] for _ in range(200005)]
ans = [0 for _ in range(n)]


def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)


for a, b in abL:
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

for p, x in pxL:
    p -= 1
    ans[p] += x

dfs(0)

for a in ans:
    print(a)

### FIXED CODE ###

import math
import sys

sys.setrecursionlimit(200005)

n, q = map(int, input().split(" "))
abL = [list(map(int, input().split(" "))) for _ in range(n - 1)]
pxL = [list(map(int, input().split(" "))) for _ in range(q)]

to = [[] for _ in range(200005)]
ans = [0 for _ in range(n + 1)]


def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)


for a, b in abL:
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

for p, x in pxL:
    p -= 1
    ans[p] += x

dfs(0)

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

if max(a)　>　sum(a) - max(a):
  print("Yes")
else
  print("No")

### FIXED CODE ###

n=input()
a=list(map(int, input().split()))
if max(a)*2 < sum(a):
    print("Yes")
else:
    print("No")
def main()
    N= input()
    A= input()
    B= input()

    If N==1:
        print("Hello World") 
    else:
        print(A+B)
        
main()

### FIXED CODE ###

def main():
    N= int(input())
    if N==1:
        print("Hello World") 
    else:
        A= int(input())
        B= int(input())
        print(A+B)

        
main()
=int(input())
a=[]
for i in range(n):
	x=int(input())
	a.append(x)
ans=0
for i in range(n-1):
	if a[i]>0:
		ans+=(a[i]//2)
		a[i]-=(a[i]//2)*2
	if a[i]>0:
		a[i+1]-=min(a[i],a[i+1])
		ans+=min(a[i],a[i+1])
if a[-1]>0:
	ans+=a[-1]//2
print(ans)


### FIXED CODE ###

s=input()
S=s.count("S")
E=s.count("E")
N=s.count("N")
W=s.count("W")
a=0
b=0
if S>0 and N>0:
	a+=1
elif S==N==0:
	a+=1
if E>0 and W>0:
	b+=1
elif E==W==0:
	b+=1
if a==b==1:
	print("Yes")
else:
	print("No")
n, k = map(int, input().split())
A = list(map(int, input().split()))
A = [-1] + A
if A[1] != 1:
    memo = [1]
    def dfs(i, town=1):
        global memo
        arrival = A[town]
        if arrival in memo:
            memo.append(arrival)
            return memo
        memo.append(arrival)
        return dfs(i+1, A[town])

    table = dfs(0, 1)
    indexes = [i for i, x in enumerate(table) if x == table[-1]]
    q = indexes[0]
    r = (k - q) % (indexes[1] - q)
    print(table[q+r])
else:
    print(1)

### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
A = [-1] + A
memo = []
loop = []
visit = [0]*n
town = 1
while visit[town-1] < 2:
    if visit[town-1] == 0:
        memo.append(town)
    else:
        loop.append(town)
    visit[town-1] += 1
    town = A[town]
outlier = len(memo) - len(loop) 
T = len(loop)
if k <= outlier:
    print(memo[k])
else:
    print(loop[(k-outlier) % T])
def problem():
    N = int(input())
    H = map(int, input().split())
    print(algorithm(N,H))

def algorithm(N: int, H):
  currentMax = H[0]
  counter = 1
  for i in range(1, N):
    if currentMax <= H[i]:
      counter += 1
      currentMax = H[i]
    
  return counter

problem()

### FIXED CODE ###



def problem():
    N = int(input())
    H = list(map(int, input().split()))
    print(algorithm(N,H))


def algorithm(N: int, H):
  currentMax = H[0]
  counter = 1
  for i in range(1, N):
    if currentMax <= H[i]:
      counter += 1
      currentMax = H[i]
    
  return counter

problem()
s = input()
print(int(s.count('1'))

### FIXED CODE ###

s = input()
print(int(s.count('1')))
import sys
import bisect

def main():
  input = sys.stdin.readline
  inf = pow(10, 18)
  a, b, q = map(int, input().split())
  s = [-inf]+[int(input()) for _ in range(a)]+[inf]
  t = [-inf]+[int(input()) for _ in range(b)]+[inf]
  
  for _ in range(q):
    x = int(input())
    i = bisect.bisect_left(s, x)
    j = bisect.bisect_left(t, x)
    ans = inf
    for l in range(2):
      for m in range(2):
        sub = min([abs(x-s[i+l]), abs(x-t[j+m])])+abs(s[i+l]-t[j+m])
        if ans > sub:
          ans = sub
    print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys

def main():
  input = sys.stdin.readline
  a, b, q = map(int, input().split())
  s = [0]*a
  for i in range(a):
    s[i] = int(input())
  
  t = [0]*b
  for i in range(b):
    t[i] = int(input())

  s_near = [0]*a
  k = 0
  for i in range(a):
    if k == b-1:
      s_near[i] = abs(s[i]-t[b-1])
      continue
    while True:
      sub = min([abs(s[i]-t[k]), abs(s[i]-t[k+1])])
      if sub == abs(s[i]-t[k+1]):
        k += 1
        if k == b-1:
          s_near[i] = sub
          break
        continue
      else:
        s_near[i] = sub
        break
  
  t_near = [0]*b
  k = 0
  for i in range(b):
    if k == a-1:
      t_near[i] = abs(t[i]-s[a-1])
      continue
    while True:
      sub = min([abs(t[i]-s[k]), abs(t[i]-s[k+1])])
      if sub == abs(t[i]-s[k+1]):
        k += 1
        if k == a-1:
          t_near[i] = sub
          break
        continue
      else:
        t_near[i] = sub
        break
  
  
  for i in range(q):
    x = int(input())
    if x <= s[0]:
      sub1 = s[0]-x+s_near[0]
    elif x >= s[a-1]:
      sub1 = x-s[a-1]+s_near[a-1]
    else:
      l, r = 0, a
      while r-l > 1:
        k = (r+l)//2
        if x <= s[k]:
          r = k
        else:
          l = k
      sub1 = min([s[r]-x+s_near[r], x-s[l]+s_near[l]])
    
    
    if x <= t[0]:
      sub2 = t[0]-x+t_near[0]
    elif x >= t[b-1]:
      sub2 = x-t[b-1]+t_near[b-1]
    else:
      l, r = 0, b
      while r-l > 1:
        k = (r+l)//2
        if x <= t[k]:
          r = k
        else:
          l = k
      sub2 = min([t[r]-x+t_near[r], x-t[l]+t_near[l]])
    ans = min([sub1, sub2])
    print(ans)


if __name__ == "__main__":
  main()
a=input()
b=input()
s=int(a)*int(b)
t=int(a)*2+int(b)*2
print(s, t)


### FIXED CODE ###

a, b = map(int, input().split())
s=int(a)*int(b)
t=(int(a)+int(b))*2
print(s, t)
n = int(input())
w = []
for i in range(n):
    item = str(input())
    if i == 0:
        w.append(item)
    elif i!=0:
        if w[i-1][-1]==item[0]:
            w.append(item)
        else:
            print("No")
            end()
l = set(w)
if len(l)==len(w):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = int(input())
w = []
for i in range(n):
    item = str(input())
    if i == 0:
        w.append(item)
    elif i!=0:
        if w[i-1][-1]==item[0]:
            w.append(item)
        elif w[i-1][-1]!=item[0]:
            print("No")
            exit()
l = set(w)
if len(l)==len(w):
    print("Yes")
else:
    print("No")
Slist=list(input())
ans=0

for i in range(len(S)):
    if ans=0 and S[i]="R":
        ans=1
for i in range(len(S)-1):
    if S[i]=="R" and S[i+1]=="R":
        ans+=1

print(ans)



### FIXED CODE ###

S=list(input())
ans=0

for i in range(len(S)):
    if ans==0 and S[i]=="R":
        ans=1
for i in range(len(S)-1):
    if S[i]=="R" and S[i+1]=="R":
        ans+=1

print(ans)
n,a,b = map(int,input().split())
count = 0
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
    

for i in range(2, n + 1):
  g1.append( ( g1[-1] * i ) % mod )
  inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
  g2.append( (g2[-1] * inverse[-1]) % mod )
for j in range(2,n + 1):
  if j == a or i == b:
    pass
  else:
    count += cmb(n, j, p)
print(count)


### FIXED CODE ###

mod = 10**9 + 7
def cmb(n,r,mod):
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod

n,a,b = map(int,input().split())
count = 0
all = pow(2,n,mod) - 1
nCa = cmb(n,a,mod)
nCb = cmb(n,b,mod)
ans = all - (nCa + nCb)
while (ans < 0):
  ans += mod
print(ans)
a,b=map(int,input_line.split())
if a==1 or b==1:
    print (1)
else:
    print (((a*b)+1)//2)

### FIXED CODE ###

a,b=map(int,input().split())
if a==1 or b==1:
    print (1)
else:
    print (((a*b)+1)//2)
from collections import Counter
N = int(input())
Dlist = list(map(int, input().split()))
DCounter = Counter(Dlist)
if DCounter[0] == 1 and Dlist[0] == 0:
    num = 1
    mae = 1
    for key, value in sorted(DCounter.items()[1:]):
        num *= (mae ** value)
        mae = value
        num %= 998244353
    print(num % 998244353)
else:
    print(0)


### FIXED CODE ###

from collections import Counter
N = int(input())
Dlist = list(map(int, input().split()))
DCounter = Counter(Dlist)
if DCounter[0] == 1 and Dlist[0] == 0:
    num = 1
    for i in range(1, max(Dlist) + 1):
        num *= DCounter[i - 1] ** DCounter[i]

    print(num % 998244353)
else:
    print(0)
n,m=map(int,input().split())
root=[i for i in range(n+1)]
rank=[0]*(n+1)
def find(x):
    if x==root(x):
        return x 
    else:
        return find(root[x])

def union(x,y):
    x=find(x)
    y=find(y)
    if rank[x]>rank[y]:
        root[y]=x 
    else rank[x]<rank[y]:
        root[x]=y
        if rank[x]==rank[y]:
            rank[y]+=1
def k_sub():
    
    p=list(map(int,input().split()))
    p=[-1]+p 
    for _ in range(m):
        x,y=map(int,input().split())
        union(x,y)
    d=[[] for i in range(n+1)]
    u=[[] for i in range(n+1)]
    for i in range(1,n+1):
        d[find[i]].append(i)
        u[find[i]].append(p[i])
    cnt=0
    for i in range(n):
        for candidate in d[i]:
            if candidate in u[i]:
                cnt+=1
    print(cnt)
if __name__=='__main__':
    k_sub()
    

### FIXED CODE ###

n,m=map(int,input().split())
p=list(map(int,input().split()))
uf={i:i for i in range(1,n+1)}
def get_p(i):
    lst=[]
    while uf[i]!=i:
        lst.append(i)
        i=uf[i]
    for l in lst[:-1]:
        uf[l]=i 
    return i 

def unite(i,j):
    uf[get_p(i)]=get_p(j)
def same(i,j):
    return get_p(i)==get_p(j)

def main():
    for i in range(m):
        x,y=map(int,input().split())
        unite(x,y)
    cnt=0
    for i in range(1,n+1):
        cnt+=same(p[i-1],uf[i])
    print(cnt)    
if __name__=='__main__':
    main()
n = int(input())
a = []
for x in input().split():
    a.append(int(x))

ans = []

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def gcd_list(numbers):
    element = gcd(numbers[0], numbers[1])
    if len(numberes)==2:
        return element
    else:
        for i in range(2, len(numbers)):
            element=gcd(element, numbers[i])
        return element

if n == 2:
    print(max(a))
else:
    for i in range(n):
        c = a.copy()
        c.remove(a[i])
        ans.append(gcd_list(c))

    print(max(ans))


### FIXED CODE ###

def gcd(x,y):
    if x<y:
        x,y=y,x
    #x>y
    if y==0:
        return x
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)

N=int(input())
A=[int(i) for i in input().split()]
X=[0 for i in range(N)]
Y=[0 for i in range(N)]
for i in range(1,N):
    X[i]=gcd(X[i-1],A[i-1])
for i in range(N-1)[::-1]:
    Y[i]=gcd(Y[i+1],A[i+1])
Z=[gcd(X[i],Y[i]) for i in range(N)]
print(max(Z))
def func(nStep:int, X) -> int:
    nStep += 1
    newX = X % bin(X).count('1')
    if newX == 0:
        return nStep
    else:
        return func(nStep, newX)

def solve():
    N = int(input())
    X = input()
    for i in range(N):
        print(func(0, int(X,2)^(1<<(N-i-1))))

if __name__ == "__main__":
    solve()

### FIXED CODE ###

def f(n):
    if n == 0:
        return 0
    return f(n % bin(n).count("1")) + 1


def solve():
    N = int(input())
    X = input()
    p = X.count("1")
    rem_plus = 0
    rem_minus = 0
    for i in range(N):
        k = N - i - 1
        if X[i] == "0":
            continue
        elif p > 1:
            rem_minus = (rem_minus + pow(2, k, p - 1)) % (p - 1)
        rem_plus = (rem_plus + pow(2, k, p + 1)) % (p + 1)
    for i in range(N):
        k = N - i - 1
        if X[i] == "0":
            print(f((rem_plus + pow(2, k, p + 1)) % (p + 1)) + 1)
        elif p > 1:
            print(f((rem_minus - pow(2, k, p - 1)) % (p - 1)) + 1)
        else:
            print(0)


if __name__ == "__main__":
    solve()
a = int(input())
x = list(map(float, input().split()))
m = max(x)
M = m/2
t = 0
s = float("INF")
for i in x:
    #print(s,abs(M-i),i,M)
    if s >= abs(M-i):
        s = min(s,abs(M-i))
        t = i
print(str(int(m))+" "+str(int(t)))

### FIXED CODE ###

a,b,c= map(int, input().split())
p = list(map(int, input().split()))
k = 0
for i in range(b):
    if p[i] < c:
        k+=1
print(min(k,b-k))
N = int(input())
w = []
ans = "Yes"
for i in range(N):
  s = str(input())
  if(i>0):
    if(s[0]==w[-1][-1]):
      None
    else:
      ans = "No"
      break
  w.append(s)
j = set(N)
l = len(list(j))
if(len(N)==l):
  None
else:
  ans="No"
print(ans)

### FIXED CODE ###

N = int(input())
w = []
ans = "Yes"
for i in range(N):
  s = str(input())
  if(i>0):
    if(s[0]==w[-1][-1]):
      None
    else:
      ans = "No"
      break
  w.append(s)
j = set(w)
l = len(list(j))
if(N==l):
  None
else:
  ans="No"
print(ans)
import itertools

N = int(input())
params = []
for i in range(N):
    xyh = [int(n) for n in input().split()]
    params.append(xyh)

#if len(params) == 1:
#    print(*params[0])

#else:

#Cx, Cy, H = 0, 0, 0
for cxi, cyi in itertools.product(range(101), range(101)):
    hight_ = params[0][2] + abs(params[0][0] - cxi) + abs(params[0][1] - cyi)

    for k in range(N):
        if params[k][2] > 0:
            hight = params[k][2] + abs(params[k][0] - cxi) + abs(params[k][1] - cyi)

            if hight < 1:
                break
            else:
                if hight != hight_:
                    break
                else:
                    hight_ = hight
                    continue

        #elif params[k][2] == 0:
        #    if 1 > (abs(params[k][0] - cxi) + abs(params[k][1] - cyi)):
        #        break
    
    else:
        Cx = cxi
        Cy = cyi
        H = hight
    
    continue

print(Cx, Cy, H)

### FIXED CODE ###

N = int(input())
params = []
for i in range(N):
    xyh = [int(n) for n in input().split()]
    params.append(xyh)

for cxi in range(101):
    for cyi in range(101):
        for k in range(N):
            if params[k][2] > 0:
                hight = params[k][2] + abs(params[k][0] - cxi) + abs(params[k][1] - cyi)

        for k in range(N):
            if params[k][2] != max((hight - abs(params[k][0] - cxi) - abs(params[k][1] - cyi)), 0):
                break
        
        else:
            print(cxi, cyi, hight)
s = list(input().split('/'))

if s[0] < 2019:
  print("Heisei")
elif s[0] == 2019:
  if s[1] < 4:
    print("Heisei)
  elif (s[1] == 4 and s[2] <= 30) or s[1] > 4:
    print("TBD")
else:
  print("TBD")

### FIXED CODE ###

s = list(input().split('/'))
s = [int(ss) for ss in s]

if s[0] < 2019:
  print("Heisei")
elif s[0] == 2019:
  if s[1] < 4 or (s[1] == 4 and s[2] <= 30):
    print("Heisei")
  else:
    print("TBD")
else:
  print("TBD")
a, b = map(int, input().split())
    if (a*b) % 2:
        print('Odd')
    else:
        print('Even')

### FIXED CODE ###

a, b = map(int, input().split())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")
def tuika(newNode,pea):
    nodes[pea].append(newNode)
    if pea != 1:
        tuika(newNode, nodes[pea][0])

n, q = map(int, input().split())
nodes = [[] for _ in range(n+1)]
nodes[1].append(0)
counts = [0 for _ in range(n+1)]

for i in range(n-1):
    pea, chi = map(int, input().split())
    nodes[chi].append(pea)
    tuika(chi, pea)

for i in range(q):
    p, q = map(int, input().split())
    if len(nodes[p]) != 1:
        for j in range(1,len(nodes[p])):
            counts[nodes[p][j]] += q
    counts[p] += q

str_counts = map(str, counts[1:])
print(' '.join(str_counts))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
import sys
def input():
    return sys.stdin.readline()[:-1]
N , Q = map(int,input().split())
graph = [[] for _ in range(N)]
point = [0] * N
for _ in range(N - 1):
    a , b = map(int,input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
#print(graph)
for _ in range(Q):
    a , b = map(int,input().split())
    a = a - 1
    point[a] += b
# dfsを用いて累積和を計算する
# 初期状態だと前の値がないためデフォルト引数に-1を代入
def dfs(now , prev = -1):
    for next in graph[now]:
        # 次のノードが前に参照した値の時はcontinue
        if next == prev:
            continue
        # 現在の値を次のポイントに加算することで累積和をとる
        point[next] += point[now]
        # 次のノードと現在のノードを引数にdfsを継続する
        dfs(next , now)

dfs(0)
print(*point)
a,p = input.split(" ")
print( (a*3+p)//2 )

### FIXED CODE ###

a,p = map(int, input().split(" "))
print( (a*3+p)//2 )
num = int(input())
data = map(int, input().split())

data.sort()

min = data[0]
max = data[-1]
avg = 0

for tmp in data:
	avg += tmp

print(min,max,avg)


### FIXED CODE ###

num = int(input())
data = list(map(int, input().split()))

min = data[0]
max = data[0]
avg = 0

for tmp in data:
        avg += tmp
        if tmp < min:
        	min = tmp
        if tmp > max:
        	max = tmp

print(min,max,avg)
# coding=utf-8

import numpy as np

A = []
n, m = map(int, raw_input().split())
for _ in xrange(n):
    A.append(map(int, raw_input().split()))
# print A

b = []
for _ in xrange(m):
    b.append(input())
# print b

Ab = [sum([A[i][j] * b[j] for j in xrange(m)]) for i in xrange(n)]
# print Ab
for x in Ab:
    print x

### FIXED CODE ###

# coding=utf-8

n, m = map(int, raw_input().split())
A = [map(int, raw_input().split()) for _ in xrange(n)]
b = [input() for _ in xrange(m)]
Ab = [sum([A[i][j] * b[j] for j in xrange(m)]) for i in xrange(n)]
for x in Ab:
    print x
import time
import random
N = int(input())
s = str(input())
maxlen = N//2
start = time.time()
def solve(tgt):
    for i in range(N-tgt*2+1):
        if s[i:i+tgt] in s[i+tgt:]:
            return True
    return False

ng = maxlen + 1
ok = 0
if N>650:
    ok = 2
first = 1
while ng-ok > 1:
    end = time.time()
    if end-start > 1.2:
        if ok >= 2000:
            assert()
        r = random.random.randint(ok,ng-1)
        print(r)
        exit()
    tgt = (ok+ng)//2
    if first == 1:
        tgt = (ok+ng)*15//16
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)


### FIXED CODE ###

from collections import defaultdict as dd
N = int(input())
s = str(input())
maxlen = N//2

def solve(tgt):
    dic = dd(int)
    st = s[tgt:2*tgt]
    dic[st] += 1
    ls = [st]
    for char in s[2*tgt:]:
        st = st[1:]+char
        dic[st] += 1
        ls.append(st)
    st = s[:tgt]
    if dic[st] > 0:
        return True
    dic[ls[0]] -= 1
    for i,char in enumerate(s[tgt:N-tgt]):
        st = st[1:]+char
        if dic[st] > 0:
            return True
        dic[ls[i+1]] -= 1
    return False

ng = maxlen + 1
ok = 0
while ng-ok > 1:
    tgt = (ok+ng)//2
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)
import sys
sys.setrecursionlimit(10**8)

A, B = map(int, input().split())

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    return gcd(b, a%b)

g = gcd(A, B)
count = 0
for i in range(2, 10**6+3):
    if g%p == 0:
        count += 1
    while g%p == 0:
        g //= p
if g != 1:
    count += 1

print(count+1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

A, B = map(int, input().split())

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    return gcd(b, a%b)

g = gcd(A, B)
count = 0
for i in range(2, 10**6+3):
    if g%i == 0:
        count += 1
    while g%i == 0:
        g //= i
if g != 1:
    count += 1

print(count+1)
import sys
N,M = map(int,input().split())
sc = [list(map(int,input().split())) for i in range(M)]

ans = [0] * N
checkd = [False] * N

for i in range(M):
    if not checkd[sc[i][0]-1]:
        checkd[sc[i][0]-1] = True
        ans[sc[i][0]-1] = sc[i][1]
    else:
        if ans[sc[i][0]-1] != sc[i][1]:
            print('-1')
            sys.exit()

if N >= 2 and checkd[0] and ans[0] == 0:
    print('-1')
    sys.exit()

real = 0
for i in ans:
    real = real * 10 + i
    
print(real)

### FIXED CODE ###

N=int(input())
X=list(map(int,input().split()))
min = 9999999999
for i in range(1,101):
    sum = 0
    for j in range(N):
        sum += (X[j] - i)**2
        
    if sum < min:
        min = sum

print(min)
l,r = input().split()
l = int(l)
r = int(r)
N = int(2019)
  
ans = (l * (l + 1)) % N
count = 0
for i in range(l,r):
  for j in range(l+1,r+1):
    if(count >= (N - 1)):
      flag = True
      break
    else if(ans > (i * j) % N):
      ans = (i * j) % N
    count += 1
  if flag:
    break
    
print(ans)

### FIXED CODE ###

l,r = input().split()
l = int(l)
r = int(r)
N = int(2019)
  
ans = N
count = 0
right = min(l + N, r)
for i in range(l,right):
  for j in range(i+1,right+1):
    ans = min(ans, (i * j) % N)
    
print(ans)
from sys import exit

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

ans = []

for i in range(M):
    L, R = map(int, input().split())

    if i == 0:
        for card in range(L, R + 1):
            ans.append(card)
        continue

    if ans[0] < L:
        for card in range(ans[0], L):
            ans.remove(card)

    if R < ans[-1]:
        for card in range(R + 1, ans[-1] + 1):
            ans.remove(card)

    if not ans:
        print(0)
        exit()

print(len(ans))


### FIXED CODE ###

from sys import exit

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

L = []
R = []

for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

l_max = max(L)
r_min = min(R)

if (r_min - l_max) < 0:
    print(0)
else:
    print(r_min - l_max + 1)