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

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

bc = []
for _ in range(M):
    B, C = map(int, input().split())
    bc.extend([C]*B)

bc = list(reversed(sorted(bc)))

for i in range(min(N, len(bc))):
    a = A[i]
    b = bc[i]
    A[i] = max(a, b)

print(sum(A))

### FIXED CODE ###

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

dic = {}
for i in range(N):
    tmp = A[i]
    if tmp in dic:
        dic[tmp] += 1
    else:
        dic[tmp] = 1

for _ in range(M):
    B, C = map(int, input().split())
    if C in dic:
        dic[C] += B
    else:
        dic[C] = B

dic = sorted(dic.items(), reverse=True)

ans, cnt = 0, 0
i = 0
while True:
    k, v = dic[i]
    cnt += v
    if cnt < N:
        ans += k*v
    elif cnt == N:
        ans += k*v
        break
    else:
        ans += k*(v - (cnt-N))
        break
    i += 1

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

import collections
import sys
sys.setrecursionlimit(10**8)

n=int(input())
arr=[input() for _ in range(n)]
g=[[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if i==j:
      continue
    if arr[i][j]=='1':
      g[i].append(j)

colors=[0]*n

def dfs(v,color):
  colors[v]=color
  for u in g[v]:
    if colors[u]==color:
      return False
    if colors[u]==0 and not dfs(u,-color):
      return False
  return True

def is_bipartite():
  return dfs(0,1)

if is_bipartite()==False:
  print(-1)
  exit()

ans=0
for v in range(n):
  q=collections.deque()
  q.append((v,1))
  checked=[0]*n
  anss=[]
  while len(q)!=0:
    tmp,depth=q.popleft()
    anss.append(depth)
    checked[tmp]=1
    for v in g[tmp]:
      if checked[v]==0:
        q.append((v,depth+1))
  ans=max(ans,max(anss))
print(ans)

### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall
import sys
sys.setrecursionlimit(10**8)

n=int(input())
arr=[input() for _ in range(n)]
g=[[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if i==j:
      continue
    if arr[i][j]=='1':
      g[i].append(j)
g2=[[0]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    g2[i][j]=int(arr[i][j])

colors=[0]*n

def dfs(v,color):
  colors[v]=color
  for u in g[v]:
    if colors[u]==color:
      return False
    if colors[u]==0 and not dfs(u,-color):
      return False
  return True

def is_bipartite():
  return dfs(0,1)

if is_bipartite()==False:
  print(-1)
  exit()

ans=0
d=floyd_warshall(g2)
for i in range(n):
  ans=max(ans,int(max(d[i])+1))
print(ans)
### BUGGY CODE ###

str = input()
Q = int(input())
for _ in range(Q):
    line = input().split()
    op1 = int(line[0])
    if op1 == 1:
        str = str[::-1]
    else:
        op2 = int(line[1])
        char = line[2]
        if op2 == 1:
            str = char + str
        else:
            str += char
print(str)


### FIXED CODE ###

"""
    Author: _YL_
"""
s = input()
n = int(input())

flip = 0
left = 0
right = 1
strs = ["", ""]

i = 0
while i < n:
    lst = input().split()

    if lst[0] == "1":
        flip += 1
        left = 0 if left == 1 else 1
        right = 0 if right == 1 else 1
    elif lst[1] == "1":
        strs[left] += lst[2]
    else:
        strs[right] += lst[2]
    i += 1

if flip % 2 == 1:
    s = s[::-1]
    
s = strs[left][::-1] + s + strs[right]

print(s)
### BUGGY CODE ###

n = int(input())
s = input()
counter = 0

for i in range(0, n-2):
  for j in range(i+1, n-1):
    for k in range(j+1, n):
      if j-i != k-j:
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
          counter += 1
    
print(counter)


### FIXED CODE ###

n = int(input())
s = input()

r = s.count('R')
g = s.count('G')
b = s.count('B')
counter = 0

for i in range(n-2):
  for j in range(i+1, n-1):
    k = 2*j - i
    if k > n-1:
      break
    if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
      counter += 1
      
print(r*g*b - counter)
### BUGGY CODE ###

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


for i in range(K):
    cum_sum = [0]*N
    for j in range(N):
        left = max(0, j - A[j])
        right = min(N-1, j+A[j])
        cum_sum[left] += 1
        if right + 1 < N:
            cum_sum[right+1] -= 1
    A[0] = cum_sum[0]
    for j in range(N-1):
        cum_sum[j+1] += cum_sum[j]
        A[j+1] = cum_sum[j+1]
    
    if A[0] == A[N-1] == N:
        break
        
for i in range(N):
    print(A[i], " ", end = "")
print()

### FIXED CODE ###

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


for i in range(min(K, 42)):
    cum_sum = [0]*N
    for j in range(N):
        left = max(0, j - A[j])
        right = min(N-1, j+A[j])
        cum_sum[left] += 1
        if right + 1 < N:
            cum_sum[right+1] -= 1
    A[0] = cum_sum[0]
    for j in range(N-1):
        cum_sum[j+1] += cum_sum[j]
        A[j+1] = cum_sum[j+1]
    
        
for i in range(N):
    print(A[i], " ", end = "")
print()
### BUGGY CODE ###

N = int(input())

def ff(n):
    ans = 0
    for x in range(1,int(-(-n**0.5//1))+1):
        for y in range(1,x+1):
            for z in range(1, y+1):
                if x*x + y*y + z*z + x*y + y*z + z*x == n:
                    if x == y and y == z and z == x:
                        ans +=1
                    elif x == y or y == z or z == x:
                        ans += 3
                    else:
                        ans += 6
    return ans
for i in range(1, N+1):
    if i <6:
        print(0)
    else:
        print(ff(i))

### FIXED CODE ###

N = int(input())
n = 10**4
tmp = [0]*((10**4)+1)
for x in range(1,int(-(-n**0.5//1))+1):
    for y in range(1,x+1):
        for z in range(1, y+1):
            if x*x + y*y + z*z + x*y + y*z + z*x <= 10**4:
                if x == y and y == z and z == x:
                    tmp[x*x + y*y + z*z + x*y + y*z + z*x] +=1
                elif x == y or y == z or z == x:
                    tmp[x*x + y*y + z*z + x*y + y*z + z*x]  += 3
                else:
                    tmp[x*x + y*y + z*z + x*y + y*z + z*x]  += 6
for i in range(1, N+1):
    print(tmp[i])
### BUGGY CODE ###

S = input()
Q = int(input())
switch = 0
for _ in range(Q):
    inp = input()
    if len(inp) == 1:
        if switch:
            switch = 0
        else:
            switch = 1
    else:
        T, F = map(int, inp.split()[:2])
        C = inp.split()[-1]
        if F == 1:
            if switch:
                S = S + C
            else:
                S = C + S
        else:
            if switch:
                S = C + S
            else:
                S = S + C
if switch:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

from collections import deque

S = deque([x for x in input()])
Q = int(input())
switch = 0
for _ in range(Q):
    inp = input()
    if len(inp) == 1:
        T = int(inp)
        if switch:
            switch = 0
        else:
            switch = 1
    else:
        T, F = map(int, inp.split()[:2])
        C = inp.split()[-1]
        if F == 1:
            if switch:
                S.append(C)
            else:
                S.appendleft(C)
        else:
            if switch:
                S.appendleft(C)
            else:
                S.append(C)
if switch:
    print("".join(list(S)[::-1]))
else:
    print("".join(S))
### BUGGY CODE ###

n, a, b = map(int, input().split())

array = []

t = 0

while t < 10 ** 100:
    for p in range(a):
        array.append('blue')
    for q in range(b):
        array.append('red')
    t += 1
    
x = 0

for i in range(n):
    if array[i] == 'blue':
        x += 1

print(x)

### FIXED CODE ###

n, a, b = map(int, input().split())

f = n // (a+b)
g = n % (a+b)

if g <= a:
    print(a * f + g)
    
else:
    print(a * (f+1))
### BUGGY CODE ###

from collections import deque
from functools import reduce

n = int(input())
colors = [0]*(n-1)
mat = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    mat[a].append((i, b))
    mat[b].append((i, a))

q = deque()
max_len = reduce(lambda a, x:max(a, len(x)), mat, 0)
q.append(0)
while len(q) > 0:
    current = q.popleft()
    cand = [i+1 for i in range(max_len)]
    current_colors = [colors[p[0]] for p in mat[current] if colors[p[0]] > 0]
    for col in current_colors:
        cand.remove(col)

    for p in mat[current]:
        if colors[p[0]] > 0:
            continue
        col = cand.pop()
        colors[p[0]] = col
        q.append(p[1])
print(max_len)
for col in colors:
    print(col)



### FIXED CODE ###

from collections import deque
from functools import reduce

n = int(input())
colors = [0]*(n-1)
mat = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    mat[a].append((i, b))
    mat[b].append((i, a))

q = deque()
max_len = reduce(lambda a, x:max(a, len(x)), mat, 0)
q.append(0)
while len(q) > 0:
    current = q.popleft()

    used_colors = set([colors[p[0]] for p in mat[current] if colors[p[0]] > 0])
    col = 1

    for p in mat[current]:
        if colors[p[0]] > 0:
            continue
        while col in used_colors:
            col += 1
        colors[p[0]] = col
        col += 1
        q.append(p[1])
print(max_len)
for col in colors:
    print(col)
### BUGGY CODE ###

n,m=map(int,input().split())
h=list(map(int,input().split()))
a=[]
b=[]
for i in range(m):
    aa,bb=map(int,input().split())
    a.append(aa-1)
    b.append(bb-1)
ans=0
t=[False]*n
for i in range(n):
    if(t[i]):continue
    flag=True
    for j in range(m):
        if(a[j]==i):
            if(h[i]<=h[b[j]]):
                flag=False
                break
            else:t[b[j]]=True
        if(b[j]==i):
            if(h[i]<=h[a[j]]):
                flag=False
                break
            else:t[a[j]]=True
    if(flag):
        ans+=1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
h=list(map(int,input().split()))
t=[]
for i in range(m):
    t.append(list(map(int,input().split())))
ans=[True]*n
for i in range(m):
    a,b=t[i]
    if(h[a-1]<=h[b-1]):
        ans[a-1]=False
    if(h[b-1]<=h[a-1]):
        ans[b-1]=False
print(ans.count(True))
### BUGGY CODE ###

import numpy as np
n,m,k=map(int,input().split())
A=[0]+list(map(int, input().split()))
B=[0]+list(map(int, input().split()))
ans=0
a=np.cumsum(np.array(A)).tolist()
b=np.cumsum(np.array(B)).tolist()
for i in range(n+1):
    if k<a[i]:
        break
    j=m
    while b[j]>k-a[i]:
        j-=1
    ans=max(ans,i+j)
print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
ans=0
a, b=[0], [0]
for i in range(n):
    a.append(a[i]+A[i])
for i in range(m):
    b.append(b[i]+B[i])
j=m
for i in range(n+1):
    if k<a[i]:
        break
    while b[j]>k-a[i]:
        j-=1
    ans=max(ans,i+j)
print(ans)
### BUGGY CODE ###

from math import *
import bisect
n, d, a = map(int, input().split())
p = []
for _ in range(n):
  p.append(tuple(map(int, input().split())))

p = sorted(p)
c=0
for i in range(n):
  x, h = p[i]
  if h <= 0: continue
  m = ceil(h/a)
  c+=m
  m = m*a
  for i in range(i+1, n):
    if x + d*2 < p[i][0]:
      break
    p[i] = (p[i][0], p[i][1] - m)
print(c)

### FIXED CODE ###

from math import *

n, d, a = map(int, input().split())
damage_diff = [0] * n
damage = 0
p = sorted(tuple(map(int, input().split())) for _ in range(n))

j = 0
c = 0

for i in range(n):
  damage -= damage_diff[i]
  
  x, h = p[i]
  h -= damage
  if h <= 0: continue
  m = ceil(h/a)
  c += m
  m = m*a
  while j < n and p[j][0] - x <= 2 * d:
    j += 1

  if j < n:
    damage_diff[j] += m
  damage += m
print(c)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 5)
def dfs(si, t):
    for subs in ['dream', 'dreamer', 'erase', 'eraser']:
        if si + len(subs) <= N and S[si:si + len(subs)] == subs:
            if si + len(subs) == N:
                print('YES')
                exit()
            else:
                dfs(si + len(subs), t + subs)


S = input()
N = len(S)
dfs(0, '')
print('NO')


### FIXED CODE ###

S = input()
lenS = len(S)

i=0
while i < lenS:
  if S[i:i+5] =='dream':
    i+=5
    if S[i:i+2] == 'er' and S[i:i+5] != 'erase':i+=2
  elif S[i:i+6] == 'eraser': i+=6
  elif S[i:i+5] == 'erase': i+=5
  else:
    print('NO')
    exit()
print('YES')
### BUGGY CODE ###

n,*h=map(int,open(0).read().split())
while len(h)>1:
    kh=set()
    for x in h:
        mn = min(h)
        md=x%mn
        if md!=0:
            kh.add(md)
        if len(kh)==mn-1:
            break
    kh.add(mn)
    h=kh
print(mn)

### FIXED CODE ###

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

n,*h=map(int,open(0).read().split())

gh=gcd(h[0],h[1])
for i in range(2,n):
    gh=gcd(h[i],gh)

print(gh)
### BUGGY CODE ###

s = list(input())
q = int(input())
for i in range(q):
    qvery = input()
    if len(qvery) == 1: #t == 1
        s = list(reversed(s))
    else:
        qq, f, c = qvery.split(' ')
        f = int(f)
        if f == 1:
            s.insert(0, c)
        else:
            s.append(c)
for i in range(len(s)):
    print(s[i], end='')
print('')

### FIXED CODE ###

s = input()
q = int(input())
rev = 0
fir = ''
end = ''
for i in range(q):
    qvery = input()
    if len(qvery) == 1: #t == 1
        rev += 1
    else:
        qq, f, c = qvery.split(' ')
        f = int(f)
        if rev % 2 == 0:
            if f == 1:
                fir += c
            else:
                end += c
        else:
            if f == 2:
                fir += c
            else:
                end += c
fir = fir[::-1]
s = fir + s + end
if rev % 2 == 1:
    s = s[::-1]
print(s)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
S = input()
Q = int(input())

for i in range(Q):
  st = input()
  if(st[0] == '1'):
    S = S[::-1]
  else:
    if(st[2] == '1'):
      nS = st[4] + S
    else:
      nS = S + st[4]
    S = nS

print(S)


### FIXED CODE ###

# -*- coding: utf-8 -*-
S = input()
Q = int(input())

flip = 0
ad1 = []
ad2 = []
for i in range(Q):
  st = input()
  if(st[0] == '1'):
    flip += 1
  else:
    if((st[2] == '1' and flip % 2 == 0) or (st[2] == '2' and flip % 2 == 1)):
      #nS = st[4] + S
      ad1.append(st[4])
    else:
      #nS = S + st[4]
      ad2.append(st[4])

ft = ''.join(ad1)
ft = ft[::-1]
ed = ''.join(ad2)

S = ft + S + ed

if(flip % 2 != 0):
  S = S[::-1]
print(S)
### BUGGY CODE ###

l, r = [ int(_) for _ in input().split() ]

ls = []

for i in range(l,r):
    for j in range(l+1,r+1):
        ls.append(i*j)
        
print(min([ x%2019 for x in ls]))

### FIXED CODE ###

#ABC 133 Remainder Minimization 2019
l, r = [ int(_) for _ in input().split() ]

ls = [2018]

for i in range(l,r):
    for j in range(i+1,r+1):
        y = (i*j) % 2019
        if (i*j) % 2019 < min(x%2019 for x in ls):
            ls.append(i*j)
        if y == 0:
            break
    if y == 0:
        break
    
print(min([ x%2019 for x in ls]))
### BUGGY CODE ###


N = int(input())
for h in range(1,3501):
    for n in range(1,3501):
        if (4*h*n-N*n-N*h) ==0:
            continue
        val =N*h*n/(4*h*n-N*n-N*h)
        if val == int(val) and val>0:
            print(h,n,int(val))
            exit(0)

### FIXED CODE ###


N = int(input())
for h in range(1,3501):
    for n in range(1,3501):
        if 1/n + 1/h > 4/N:
            continue
        if (4*h*n-N*n-N*h) ==0:
            continue
        val =N*h*n/(4*h*n-N*n-N*h)
        if val == int(val) and val>0:
            print(h,n,int(val))
            exit(0)
### BUGGY CODE ###

S=input()
Q=int(input())
for i in range(Q):
  Query=list(filter(lambda a:a!=" ",list(input())))
  if Query[0]=="1":
    S=S[::-1]
  elif Query[0]=="2":
    if Query[1]=="1":
      S=str(Query[2])+S
    elif Query[1]=="2":
      S=S+str(Query[2])
print(S)


### FIXED CODE ###

from collections import deque

S=input()
Q=int(input())
r_flag=False
ans=deque((S))
for i in range(Q):
  Qu=input().split()
  if Qu[0]=="1":
    r_flag=not r_flag
  else:
    if Qu[1]=="1":
      if r_flag==True:
        ans.append(Qu[2])
      else:
        ans.appendleft(Qu[2])
    else:
      if r_flag==True:
        ans.appendleft(Qu[2])
      else:
        ans.append(Qu[2])
ans=list(ans)
print("".join(ans) if r_flag==False else "".join(ans[::-1]))
### BUGGY CODE ###

N = int(input())
s_list=[]

for _ in range(N):
    s_list.append(input())
    
count=0
for i in range(N):
    for j in range(i+1,N):
        s1=list(s_list[i])
        s2=list(s_list[j])
        if sorted(s1)==sorted(s2):
            count+=1
print(count)

### FIXED CODE ###

N = int(input())
s_list=[]
s_dict={}
count=0

for i in range(N):
    s = "".join(sorted(input()))
    if s not in s_dict:
        s_dict[s]=0
    else:
        s_dict[s]+=1
        count+=s_dict[s]
print(count)
### BUGGY CODE ###

#通るかな？
def 解():
    import sys
    input = sys.stdin.readline

    N,Q = [int(_) for _ in input().split()]

    S = input()
    dS = {}
    for i in range(1,N+1):
        s = S[i-1]
        if s in dS:
            dS[s].add(i)
        else:
            dS[s] = {i}
    aM = [1]*(N+2)

    for _ in range(Q):
        t,d = input().split()
        if t in dS:
            if d == "R":
                for i in dS[t]:
                    aM[i+1]  += aM[i]
                    aM[i] = 0
            else:
                for i in dS[t]:
                    aM[i-1] += aM[i]
                    aM[i] = 0
    print(sum(aM[1:N+1]))
解()


### FIXED CODE ###

#こうけ？
def 解():
    import sys
    input = sys.stdin.readline
    N,Q = [int(_) for _ in input().split()]
    S = " " + input() + " "
    aC = [[ _.rstrip() for _ in  _.split()] for _ in sys.stdin.readlines()]
    iL = 0
    iR = N+1
    for t,d in aC[::-1]:
        if t == S[iL+1] and d == "L" and iL < N+1:
                iL += 1
        elif t == S[iL] and d == "R" and 0 < iL:
                iL -= 1

        if t == S[iR-1] and d == "R" and 0 < iR:
                iR -= 1
        elif t == S[iR] and d == "L" and  iR < N+1:
                iR += 1
    if iL < iR:
        print(iR-iL-1)
    else:
        print(0)
解()
### BUGGY CODE ###

n,m,k = map(int,input().split())
mod = 998244353
ans = 0

def comb(n,k,mod):
    nCk = 1

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= mod
 
    for i in range(1,k+1):
        nCk *= pow(i,mod-2,mod)
        nCk %= mod
    return nCk
for i in range(k+1):
    a = pow(m-1, n-i-1, mod)
    b = comb(n-1,i,mod)
    ans += a*b
ans *= m
print(ans%mod)

### FIXED CODE ###

n,m,k = map(int,input().split())
mod = 998244353
ans = 0

def comb(n, r, mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
  
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, n+1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)


for i in range(k+1):
    a = pow(m-1, n-i-1, mod)
    b = comb(n-1,i,mod)
    ans += (a*b)%mod
ans *= m
print(ans%mod)
### BUGGY CODE ###

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

x = []
for i in range(m):
  x.append(list(map(str,input().split())))
  
qu,ju = [],[]
AC,WA = 0,0
for i in x:
  qu.append(i[0])
  ju.append(i[1])

qu = list(set(qu))
for i in qu:
  x_target = [j for j in x if j[0] == i]
  
  #ACがあるかどうか、あった場合そのインデックス
  if [i,"AC"] in x_target:
    index = x_target.index([i,"AC"])
    WA += index
    AC += 1
  else:
    pass
  
print(AC, WA)

### FIXED CODE ###

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

ac = [0]*n
wa = [0]*(n+1)
pena = 0

for i in range(m):
  ques, state = input().split()
  ques = int(ques)-1
  
  if (state=="AC") and (ac[ques]==0):
    ac[ques] = 1
    pena += wa[ques]
  elif (state=="WA") and (ac[ques]==0):
    wa[ques] += 1
    
print(sum(ac), pena)
### BUGGY CODE ###

H, W, K = map(int, input().split())
s = [list(input()) for _ in range(H)]

c = [[0 for _ in range(W)] for _ in range(H)]

# 1×ｗの一次元の配列で考える。分割したマスをそれぞれホワイトチョコをカウントする
# データを加工してから貪欲法を行う

# bit全探索: 横線で割るパターン全てについて、縦線での折り方を考える
ans = (H-1) * (W-1)
for div in range(1<<(H-1)):
    g = 0 # g: 横線で分割するグループ番号（０、１、２...）
    id = [0] * H #何行目であるかを識別するid: i=1なら　グループiになる
    for i in range(H):
        id[i] = g
        if div>>i&1: # 2進法でdivのi桁目が1の時、そこで分割する
            g += 1 #分割線がきたらgを増やす
    g += 1 # グループ数は分割線+１になる
    #　集計に使うｃ配列を初期化
    for i in range(g):
        for j in range(W):
            c[i][j] = 0
    # グループごとを各列ごとのホワイトチョコを集計する
    for i in range(H):
        for j in range(W):
            c[id[i]][j] += int(s[i][j])

    num = g - 1 #すでに横線で折った回数（グループ数-１）
    now = [0] * g #現状で何個のホワイトチョコがあるか
    # 各グループの縦割りの確認
    def add(j):
        for i in range(g):
            now[i] += c[i][j] #ｊ列目のホワイトチョコを足していく
        for i in range(g):
            
            if now[i] > K: return False
        return True

    for j in range(W):
        if not (add(j)): # ホワイトチョコがKを超えていれば、縦で織る。
            num += 1
            now = [0] * g
            if not (add(j)):
                num = (H-1) * (W-1)
                break
    #print(g, c, num) # 横割りの回数、各グループの集計、最終的に折った回数
    ans = min(ans, num) # 割った回数値の最小を更新 

print(ans)

### FIXED CODE ###

H, W, K = map(int, input().split())
s = [list(input()) for _ in range(H)]

c = [[0 for _ in range(W)] for _ in range(H)]

# 1×ｗの一次元の配列で考える。分割したマスをそれぞれホワイトチョコをカウントする
# データを加工してから貪欲法を行う

# bit全探索: 横線で割るパターン全てについて、縦線での折り方を考える
ans = (H-1) * (W-1)
for div in range(1<<(H-1)):
    g = 0 # g: 横線で分割するグループ番号（０、１、２...）
    id = [0] * H #何行目であるかを識別するid: i=1なら　グループiになる
    for i in range(H):
        id[i] = g
        if div>>i&1: # 2進法でdivのi桁目が1の時、そこで分割する
            g += 1 #分割線がきたらgを増やす
    g += 1 # グループ数は分割線+１になる
    #　集計に使うｃ配列を初期化
    for i in range(g):
        for j in range(W):
            c[i][j] = 0
    # グループごとを各列ごとのホワイトチョコを集計する
    for i in range(H):
        for j in range(W):
            c[id[i]][j] += int(s[i][j])

    num = g - 1 #すでに横線で折った回数（グループ数-１）
    now = [0] * g #現状で何個のホワイトチョコがあるか
    # 各グループの縦割りの確認
    def add(j):
        for i in range(g):
            now[i] += c[i][j] #ｊ列目のホワイトチョコを足していく
        for i in range(g):
            
            if now[i] > K: return False
        return True

    for j in range(W):
        if not (add(j)): # ホワイトチョコがKを超えていれば、縦で織る。
            num += 1
            now = [0] * g
            if not (add(j)):
                num = (H-1) * (W-1)
                break
    #print(g, c, num) # 横割りの回数、各グループの集計、最終的に折った回数
    ans = min(ans, num) # 割った回数値の最小を更新 

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

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A_num = [0] * N
    for a in A:
        A_num[a-1] += 1
        
    A_product = [0] * N
    A_product_1 = [0] * N
    for i in range(N):
        a = A_num[i]
        A_product[i] = int(a * (a-1) / 2)
        if a == 0:
            A_product_1[i] = 0
        else:
            A_product_1[i] = int((a-1) * (a-2) / 2)

    for k in A:
        s = sum(A_product) - A_product[k-1] + A_product_1[k-1]
        print(s)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A_num = [0] * N
    for a in A:
        A_num[a-1] += 1

    A_product = [0] * N
    A_product_1 = [0] * N
    for i in range(N):
        a = A_num[i]
        A_product[i] = int(a * (a-1) / 2)
        if a == 0:
            A_product_1[i] = 0
        else:
            A_product_1[i] = int((a-1) * (a-2) / 2)


    su = sum(A_product)
    for k in A:
        print(su - A_product[k-1] + A_product_1[k-1])


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

import math

n = int(input())
l = list(map(int, input().split()))
ans = 0
l.sort()

for i in range(n-2):
    for j in range(i+1, n-1):
        buf = l[i]+l[j]
        Min = j+1
        Max = n
        while(Min!=Max):
            Mid = math.floor((Min+Max)/2)
            if l[Mid] < buf:
                Min = Mid+1
            elif l[Mid] == buf:
                Min = Mid
                Max = Mid
            else:
                Max = Mid
        ans += Min-(j+1)
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
ans = 0
l.sort()

for i in range(n-2):
    for j in range(i+1, n-1):
        c_i = bisect.bisect_left(l, l[i]+l[j])
        if c_i > j:
            ans += c_i - j - 1
        else:
            continue
print(ans)