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

N, M = [int(i) for i in input().split(" ")]
p = list()
y = list()
yd = {}
for i in range(0, M):
    pi, yi = [int(i) for i in input().split(" ")]
    p.append(pi)
    y.append(yi)
    if pi in yd.keys():
        yd[pi].append(yi)
    else:
        yd[pi] = [yi]

ydid = {}
for i in range(0, M):
    num = 1
    for j in sorted(yd[p[i]]):
        ydid[j] = num
        num = num + 1

for i in range(0, M):
    print("{:06}{:06}".format(p[i], ydid[y[i]]))

### FIXED CODE ###

N, M = [int(i) for i in input().split(" ")]
p = list()
y = list()
yd = {}
for i in range(0, M):
    pi, yi = [int(i) for i in input().split(" ")]
    p.append(pi)
    y.append(yi)
    if pi in yd.keys():
        yd[pi].append(yi)
    else:
        yd[pi] = [yi]

ydid = {}
for i in yd.keys():
    num = 1
    for j in sorted(yd[i]):
        ydid[j] = num
        num = num + 1

for i in range(0, M):
    print("{:06}{:06}".format(p[i], ydid[y[i]]))
### BUGGY CODE ###

#!/usr/bin/python

# AtCoder Beginner Contest 075
# D - Axis-Parallel Rectangle

from sys import stdin

def nPointsInRect(y0, y1, points):
  return len([p for p in points if y0 <= p[1] <= y1])

def solve(K, points):
  points.sort()  # sort the points by x-coordinates
  xs = [p[0] for p in points]          # sorted x-coordinates
  ys = sorted([p[1] for p in points])  # sorted y-coordinates
  minArea = (xs[-1] - xs[0]) * (ys[-1] - ys[0])  # the biggest rect
  for i0 in range(len(points)):
    for i1 in range(i0 + K - 1, len(points)):
      for j in range(len(ys)):
        y0 = ys[j]
        for y1 in ys[j + K - 1:]:
          if nPointsInRect(y0, y1, points[i0 : i1 + 1]) >= K:
            area = (xs[i1] - xs[i0]) * (y1 - y0)
            minArea = min(minArea, area)
  return minArea

def splitToInt(line):
  words = line.strip().split()
  return [int(w) for w in words]

N, K = splitToInt(stdin.readline())
points = []
for i in range(N):
  x, y = splitToInt(stdin.readline())
  points.append((x, y))
print(solve(K, points))

### FIXED CODE ###

#!/usr/bin/python

# AtCoder Beginner Contest 075
# D - Axis-Parallel Rectangle

from sys import stdin

def nPointsInRect(y0, y1, points):
  return len([p for p in points if y0 <= p[1] <= y1])

def solve(K, points):
  points.sort()  # sort the points by x-coordinates
  xs = [p[0] for p in points]          # sorted x-coordinates
  ys = sorted([p[1] for p in points])  # sorted y-coordinates
  minArea = (xs[-1] - xs[0]) * (ys[-1] - ys[0])  # the biggest rect
  for i0 in range(len(points)):
    for i1 in range(i0 + K - 1, len(points)):
      for j in range(len(ys)):
        y0 = ys[j]
        for y1 in ys[j + K - 1:]:
          if nPointsInRect(y0, y1, points[i0 : i1 + 1]) >= K:
            area = (xs[i1] - xs[i0]) * (y1 - y0)
            minArea = min(minArea, area)
            break  # no other rects for the same i0, i1, y0 are unnecessary
  return minArea

def splitToInt(line):
  words = line.strip().split()
  return [int(w) for w in words]

N, K = splitToInt(stdin.readline())
points = []
for i in range(N):
  x, y = splitToInt(stdin.readline())
  points.append((x, y))
print(solve(K, points))
### BUGGY CODE ###

N=int(input())
S=input()
r=[1 if S[0]=="R" else 0]
g=[1 if S[0]=="G" else 0]
b=[1 if S[0]=="B" else 0]

for i in range(1,N):
  if S[i]=="R":
    r.append(r[-1]+1)
    g.append(g[-1])
    b.append(b[-1])
  elif S[i]=="G":
    r.append(r[-1])
    g.append(g[-1]+1)
    b.append(b[-1])
  else:
    r.append(r[-1])
    g.append(g[-1])
    b.append(b[-1]+1)

#print(r)
#print(g)
#print(b)

st={"R","G","B"}

def calc(i,j):
  tmp={i,j}
  ans=st-tmp
  return ans.pop()

#print(calc("R","G"))
ans=0

for i in range(0,N-2):
  for j in range(i+1,N-1):
    if S[j]==S[i]:
      pass
    else:            
      tmp=calc(S[i],S[j])
      if tmp=="R":
        #print(i,j,tmp,r[-1],r[j])
        ans += r[-1]-r[j]
        if j+(j-i)<=N-1:
          if S[j+(j-i)]==tmp:
            ans -=1
      elif tmp=="G":
        #print(i,j,tmp,g[-1],g[j])
        ans += g[-1]-g[j]
        if j+(j-i)<=N-1:
          if S[j+(j-i)]==tmp:
            ans -=1
      else:
        #print(i,j,tmp,b[-1],b[j])
        ans += b[-1]-b[j]
        if j+(j-i)<=N-1:
          if S[j+(j-i)]==tmp:
            ans -=1

print(ans)

### FIXED CODE ###

N=int(input())
S=input()
r=[1 if S[0]=="R" else 0]
g=[1 if S[0]=="G" else 0]
b=[1 if S[0]=="B" else 0]

for i in range(1,N):
  if S[i]=="R":
    r.append(r[-1]+1)
    g.append(g[-1])
    b.append(b[-1])
  elif S[i]=="G":
    r.append(r[-1])
    g.append(g[-1]+1)
    b.append(b[-1])
  else:
    r.append(r[-1])
    g.append(g[-1])
    b.append(b[-1]+1)

#print(r)
#print(g)
#print(b)

st={"R","G","B"}

def calc(i,j):
  tmp={i,j}
  ans=st-tmp
  return ans.pop()

#print(calc("R","G"))
ans=0

for i in range(0,N-2):
  for j in range(i+1,N-1):
    if S[j]==S[i]:
      pass
    else:            
      tmp=calc(S[i],S[j])
      if tmp=="R":
        #print(i,j,tmp,r[-1],r[j])
        ans += r[-1]-r[j]
        if j+(j-i)<=N-1:
          if S[j+(j-i)]==tmp:
            ans -=1
      elif tmp=="G":
        #print(i,j,tmp,g[-1],g[j])
        ans += g[-1]-g[j]
        if j+(j-i)<=N-1:
          if S[j+(j-i)]==tmp:
            ans -=1
      else:
        #print(i,j,tmp,b[-1],b[j])
        ans += b[-1]-b[j]
        if j+(j-i)<=N-1:
          if S[j+(j-i)]==tmp:
            ans -=1

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

#! -*- coding:utf-8 -*-
n = int(input())
a = map(int,input().split())
a = list(a)
x = []

count = 0
for i in range(n):
    if count % 2 == 1:
        x.append(a[i])
    else:
        x.insert(0,a[i])

    count += 1

if n % 2 == 0:
    x.reverse()
    x = map(str,x)
    print(' '.join(x))

else:
    x = map(str,x)
    print(' '.join(x))


### FIXED CODE ###

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

b = [0] * n
center = n // 2
for i in range(n):
    if i % 2 == 0:
        b[center + (i//2)] = arr[i]
    else:
        b[center - ((i+1)//2)] = arr[i]

if n % 2 == 0:
    pass
else:
    b.reverse()

for i in range(n-1):
    print(b[i], end = ' ')
print(b[-1])
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
#start = time.clock()
#i = 0
a,b=[],[]
check = re.compile('insert')
n=input()
#while True:
for x in xrange(n):
    (i,f)=map(str, raw_input().split())
    if check.search(i):
        a.append(f)
    else:
        b.append(f)
#print a
#print b
#for y in b:
        if f in a:
            print 'yes'
        else:
            print 'no'

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
#start = time.clock()
#i = 0
#check = 'insert'
n=input()
a=set()
for x in xrange(n):
    (i,f)=map(str, raw_input().split())
    if i=='insert':
        a.add(f)
    else:
        if f in a:
            print 'yes'
        else:
            print 'no'
### BUGGY CODE ###

from fractions import*
_,a=open(0)
a=list(map(int,a.split()))
s=1
for i in a:s*=i//gcd(s,i)
print(sum(s//i for i in a)%(10**9+7))

### FIXED CODE ###

from fractions import*
from functools import*
M=10**9+7
_,a=open(0)
*a,=map(int,a.split())
s=reduce(lambda x,y:x//gcd(x,y)*y,a)%M
c=0
for i in a:
    c+=s*pow(i,M-2,M)
    c%=M
print(c)
### BUGGY CODE ###

import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

def max(a, b):
    return a if a > b else b
 
def is_match(string, pattern):
    # print(string, pattern)
    pat_len = len(pattern)
    skip = [pat_len for _ in range(256)]
    for i in range(pat_len):
        skip[ord(pattern[i])] = pat_len - i - 1
    i = pat_len - 1
    while i < len(string):
        j = pat_len - 1
        while string[i] == pattern[j]:
            if j == 0:
                return True
            i -= 1
            j -= 1
        i = i + max(skip[ord(string[i])], pat_len-j)
    return None


def main():
    N = int(input())
    S = input()

    dp = [0] * N

    for i in range(1, N):
        length = dp[i - 1] + 1
        match_string = S[i - length + 1: i + 1]
        matched_string = S[:i+1-length]
        # print(match_string, matched_string)
        if is_match(matched_string, match_string):
            dp[i] = dp[i - 1] + 1
        else:
            dp[i] = dp[i - 1]
        # print(dp[i])
    
    # print(dp)
    print(dp[-1])



if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

def max(a, b):
    return a if a > b else b
 
def is_match(string, pattern):
    # print(string, pattern)
    # pat_len = len(pattern)
    # skip = [pat_len for _ in range(256)]
    # for i in range(pat_len):
    #     skip[ord(pattern[i])] = pat_len - i - 1
    # i = pat_len - 1
    # while i < len(string):
    #     j = pat_len - 1
    #     while string[i] == pattern[j]:
    #         if j == 0:
    #             return True
    #         i -= 1
    #         j -= 1
    #     i = i + max(skip[ord(string[i])], pat_len-j)
    # return None
    if pattern in string:
        return True
    else:
        return False


def main():
    N = int(input())
    S = input()

    dp = [0] * N

    for i in range(1, N):
        length = dp[i - 1] + 1
        match_string = S[i - length + 1: i + 1]
        matched_string = S[:i+1-length]
        # print(match_string, matched_string)
        if is_match(matched_string, match_string):
            dp[i] = dp[i - 1] + 1
        else:
            dp[i] = dp[i - 1]
        # print(dp[i])
    
    # print(dp)
    print(dp[-1])



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

import bisect, heapq
n,m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)


b = []
for i in range(m):
	x, y = map(int, input().split())
	b.append([x,y])

for i in range(m):
	c = []
	for j in range(b[i][0]):
		x = heapq.heappop(a)
		if x >= b[i][1]:
			c.append(x)
			break
		x = b[i][1]
		c.append(x)
	for j in c:
		heapq.heappush(a,j)
print (sum(a))


### FIXED CODE ###

import heapq
from collections import defaultdict
n, m =map(int, input().split())
a=list(map(int, input().split()))

for i in range(n):
  a[i] *= -1


pri=list(set(a))
heapq.heapify(pri)
dict=defaultdict(int)
for i in a:
  dict[-i] += 1
for i in range(m):
  b, c = map(int, input().split())
  dict[c] += b
  heapq.heappush(pri,-c)
# print (pri)
# print (dict)

ans = 0
cnt = 0
old = 0
while True:
  x = heapq.heappop(pri)
  x *= -1
  if old == x:
    continue
  if cnt+dict[x] > n:
    ans += (n-cnt)*x
    cnt += n-cnt
  else:
    ans += dict[x]*x
    cnt += dict[x]
  if cnt >= n:
    break
  old = x
print (ans)
### BUGGY CODE ###

n, s = map(int, input().split())
a  = list(map(int, input().split()))
MOD = 998244353

dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for j in range(s+1):
        dp[i+1][j] = dp[i+1][j] + dp[i][j] * 2
        dp[i+1][j] = dp[i+1][j] % MOD
        if j + a[i] <= s:
            dp[i+1][j+a[i]] = dp[i+1][j+a[i]] + dp[i][j]
            dp[i+1][j+a[i]] = dp[i+1][j+a[i]] % MOD

print(dp[n][s])


### FIXED CODE ###

n, s = map(int, input().split())
a  = list(map(int, input().split()))
MOD = 998244353
 
dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 1
 
for i in range(n):
    for j in range(s+1):
        dp[i+1][j] = dp[i+1][j] + dp[i][j] * 2
        dp[i+1][j] = dp[i+1][j] % MOD
        if j + a[i] <= s:
            dp[i+1][j+a[i]] = dp[i+1][j+a[i]] + dp[i][j]
            dp[i+1][j+a[i]] = dp[i+1][j+a[i]] % MOD
 
print(dp[n][s])
### BUGGY CODE ###

import math
n,k = map(int,input().split())
als = list(map(int,input().split()))
als.sort()
# n = 10**5
# k = 5*(10**4) 
mod = 10**9+7
ans = 0
def nCr(n,r):
    mod = (10**9)+7
    fac = [1,1]+[0]*n
    finv = [1,1]+[0]*n
    inv = [1,1]+[0]*n
    for i in range(2,n+1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
    ans = fac[n] * (finv[r] * finv[n-r] % mod) % mod
    return ans

for i in range(n):
    if i >= k-1:
        ans += als[i] * nCr(i,k-1) % mod
        ans = ans % mod
    if i <= n-k:
        ans -= als[i] * nCr(n-i-1,k-1) % mod
        ans = ans % mod

print(ans)
        

### FIXED CODE ###

import math
n,k = map(int,input().split())
als = list(map(int,input().split()))
als.sort()
# n = 10**5
# k = 5*(10**4) 
mod = 10**9+7
ans = 0
# def nCr(n,r):
#     mod = (10**9)+7
#     fac = [1,1]+[0]*n
#     finv = [1,1]+[0]*n
#     inv = [1,1]+[0]*n
#     for i in range(2,n+1):
#         fac[i] = fac[i-1] * i % mod
#         inv[i] = mod - inv[mod%i] * (mod//i) % mod
#         finv[i] = finv[i-1] * inv[i] % mod
#     ans = fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
#     return ans

fac = [1,1]+[0]*n
finv = [1,1]+[0]*n
inv = [1,1]+[0]*n
for i in range(2,n+1):
    fac[i] = fac[i-1] * i % mod
    inv[i] = mod - inv[mod%i] * (mod//i) % mod
    finv[i] = finv[i-1] * inv[i] % mod

for i in range(n):
    if i >= k-1:
        ans += als[i] * fac[i] * (finv[(k-1)] * finv[i-(k-1)] % mod) % mod
        ans = ans % mod
    if i <= n-k:
        ans -= als[i] * fac[(n-i-1)] * (finv[(k-1)] * finv[(n-i-1)-(k-1)] % mod) % mod
        ans = ans % mod

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

import numpy as np

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

MOD = 10**9 + 7

# format関数で10進数から2進数に変換
max_digits = len(format(max(a), 'b'))  # 最大桁数

# 各位の1の数を記録していく
counter = []
for i in range(n):
    counter.append(list(format(a[i], 'b').zfill(max_digits))[::-1])  # 逆順にする 
cnt_arr = np.array(counter, dtype='int')

ans = 0
for i in range(max_digits):
    # 各位ごとの合計は2**k × 1の数 × 0の数
    one_num = np.count_nonzero(cnt_arr[:, i]) % MOD
    ans += (2**i * one_num * (n - one_num)) % MOD
print(ans % MOD)

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))

max_digits = 60
MOD = 10**9 + 7

ans = 0
for i in range(max_digits):
    one_num = np.count_nonzero((a >> i) & 1)
    radix_mod = 2**i % MOD
    ans += (radix_mod * one_num * (n - one_num)) % MOD
print(ans%MOD)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans =[]
for i in range(1,N+1):
    AN = A.index(i)
    ans.append(AN+1)
ans2 = [str(ans[i]) for i in range(len(ans))]
print(" ".join(ans2))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
AN = list(enumerate(A))
sAN = sorted(AN, key=lambda x: x[1])
ans = []
for i in range(N):
    ans.append(sAN[i][0]+1)
ans2 = [str(ans[i]) for i in range(len(ans))]
print(" ".join(ans2))
### BUGGY CODE ###

import fractions
import sys
input = sys.stdin.readline
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
count=a[0]
for i in range(n-1):
    count=count*a[i+1]//fractions.gcd(count, a[i+1])
ans=0


for i in range(n):
    ansa=count//a[i]
    ans+=ansa
    ans%=mod
print(ans)

### FIXED CODE ###

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

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

count=a[0]
for i in range(n-1):
    count=lcm(count,a[i+1])
ans=0
for i in range(n):
    ansa=count//a[i]
    ans+=ansa
    
print(ans%mod)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split()))
dic = {i:A.index(i)+1 for i in A}

print(' '.join([str(e[1]) for e in sorted(dic.items())]))

### FIXED CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split()))
rank = {}
for i in range(N):
    rank[A[i]] = str(i+1)
    
print(' '.join(rank.values()))
### BUGGY CODE ###

s = input()
K = int(input())
list = ["zzz" for i in range(K)]
for i in range(len(s)):
    for j in range(len(s)-i):
        if len(list) < K or s[i : i+j+1] < list[K-1]:
            # sSet.add(s[i : i+j+1]
            if all([k != s[i : i+j+1] for k in list]):
                list[K-1] = s[i : i+j+1]
                list.sort()
print(list[K - 1])


### FIXED CODE ###

s = input()
K = int(input())
list = ["zzz" for i in range(K)]
for i in range(len(s)):
    for j in range(len(s)-i):
        if j > 5:
            continue
        if len(list) < K or s[i : i+j+1] < list[K-1]:
            if not s[i : i+j+1] in list:
                list[K-1] = s[i : i+j+1]
                list.sort()
print(list[K - 1])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
res = A[0]
for i in range(1,len(A)): 
	res *= A[i]
if res <= 10**18:
	print(res)
else:
	print("-1")


### FIXED CODE ###

a=int(input())
b=input().split(" ")
sum1=1
 
if "0" in b:
    print("0")
else:
    for i in range(a):
        sum1=sum1*int(b[i])
        if sum1>10**18:
            sum1=-1
            break
    print(sum1)
### BUGGY CODE ###

def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    x=input().rstrip()
    p=x.count("1")
    minus=0
    plus=0
    for i in range(n):
        if x[-i-1]=="1":
            plus+=2**i
            plus%=(p+1)
    if p!=1:
        for i in range(n):
            if x[-i-1]=="1":
                minus+=2**i
                minus%=(p-1)

    def popcnt(x):
        cnt=str(bin(x)).count("1")
        x%=cnt
        return x

    for i in range(n):
        if x[i]=="0":
            amari=(plus+2**(n-i-1)%(p+1))%(p+1)
            ans=1
            while amari>=1:
                amari=popcnt(amari)
                ans+=1
            print(ans)
        else:
            if p==1:
                print(0)
                continue
            amari=(minus-2**(n-i-1)%(p-1))%(p-1)
            ans=1
            while amari>=1:
                amari=popcnt(amari)
                ans+=1
            print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
x=input().rstrip()
x10=int(x,2)
pcx=x.count("1")

plus=x10%(pcx+1)
if pcx>=2:
    minus=x10%(pcx-1)

def popcnt(x):
    cnt=1
    while x>=1:
        x%=(bin(x).count("1"))
        cnt+=1
    return cnt

for i in range(n):
    if x[i]=="0":
        amari=(plus+pow(2,n-i-1,pcx+1))%(pcx+1)
        print(popcnt(amari))
    else:
        if pcx==1:
            print(0)
        else:
            amari=(minus-pow(2,n-i-1,pcx-1))%(pcx-1)
            print(popcnt(amari))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import heapq

def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):

    h = []
    [heapq.heappush(h,-c) for b,c in zip(B, C) for b_ in range(b)]
    [heapq.heappush(h,-a) for a in A]
    k = [heapq.heappop(h) for _ in range(N)]
    print(sum(k)*-1)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, A, B, C)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):

    # bc = [c for b,c in zip(B, C) for b_ in range(b)]
    # print(A+bc)
    # k = sorted(A+bc)[-N:]
    a = [(l, 1) for l in A]
    for x, y in zip(C, B):
        a.append((x,y))


    n = N
    ans = 0
    for x, y in sorted(a, reverse=True):
        if n >= y:
            n -= y
            ans += x*y
        else:
            ans += x*n
            break
    
    print(ans)

    # print(sum(k))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, A, B, C)

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

from math import ceil
s = input().split(" ")
n = int(s[0])
k = int(s[1])
w = []
total = 0
for i in range(n):
    a = int(input())
    w.append(a)
    total += a
mx = max(ceil(total / k), max(w))
while True:
    t = []
    t.append(w[0])
    for i in range(1,len(w)):
        if t[len(t)-1] + w[i] <= mx:
            t[len(t)-1] += w[i]
        else:
            t.append(w[i])
            if len(t) > k:
                break
    if len(t) > k:
        mx += 1
    else:
        break
print(mx)

### FIXED CODE ###

def check(P,w,n):
    i = 0
    for j in range(k):
        s = 0
        while s + w[i] <= P:
            s += w[i]
            i += 1
            if i == n:
                return n
    return i

s = input().split(" ")
n = int(s[0])
k = int(s[1])
w = []
for i in range(n):
    a = int(input())
    w.append(a)

left = 0
right = 100000 * 10000
while right - left > 1:
    mid = int((right + left) / 2)
    v = check(mid,w,n)
    if v >= n:
        right = mid
    else:
        left = mid
print(right)
### BUGGY CODE ###

N, Q = map(int, input().split())
in_str_root = input()
l = []
r = []
for i in range(Q):
    in1, in2 = map(int, input().split())
    l.append(in1)
    r.append(in2)

for i in range(Q):
    in_str = in_str_root[l[i]-1:r[i]]
    #print(in_str)
    AC_count = 0
    searching_a = 1
    searching_c = 0
    for j in range(len(in_str)):
        if searching_a == 1 and in_str[j] == "A":
            searching_a =0
            searching_c = 1
        elif searching_c == 1 and in_str[j] == "C":
            AC_count +=1
            searching_a =1
            searching_c = 0
        else :
            searching_a =1
            searching_c = 0
    print(AC_count)

### FIXED CODE ###

N, Q = map(int, input().split())
in_str = input()
AC_count = []
r = [0]*(N+1)
for i in range(N):
    r[i+1] = r[i] + (1 if in_str[i:i+2] == "AC" else 0) 
    
    
for i in range(Q):
    in1, in2 = map(int, input().split())
    print(r[in2-1]-r[in1-1])
### BUGGY CODE ###

MOD = 10**9+7

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

Ci = n
Si = n
Ai = 0
Bi = 0

if a == 1:
    Ai = Ci
if b == 1:
    Bi = Ci
    
for k in range(2,n+1):
    Ci = Ci*(n-k+1)//k
    Ci %= MOD
    Si += Ci
    Si %= MOD
    if k == a:
        Ai = Ci
    if k == b:
        Bi = Ci

ans = (Si - Ai - Bi) % MOD
print(ans)

### FIXED CODE ###

MOD = 10**9+7

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

Sn = pow(2,n,MOD) - 1
if a > b:
    a,b = b,a
Xa, Xb = 1,1
Ya, Yb = 1,1
for i in range(b):
    if i < a:
        Xa = ( Xa * (n-i) ) % MOD
        Ya = ( Ya * pow((a-i),MOD-2, MOD)) % MOD
    Xb = ( Xb * (n-i) ) % MOD
    Yb = ( Yb * pow((b-i),MOD-2, MOD)) % MOD

ans = Sn - Xa*Ya % MOD - Xb*Yb % MOD
while ans < 0:
    ans += MOD
    
print(ans)
### BUGGY CODE ###

from collections import Counter

n=int(input())
S=[]
ans=0
for i in range(n):
    s=input()
    S.append(s)
    for j in range(i):
        if Counter(S[j])==Counter(s):
            ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
a=set()
b=[]
import collections
for i in range(n):
    s=input()
    s=sorted(s)
    a.add("".join(s))
    b.append("".join(s))
ans=0
a=list(a)
c=collections.Counter(b)
for i in range(len(a)):
    ans+=c[a[i]]*(c[a[i]]-1)//2
print(ans)