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

N, Y = map(int, input().split())
number =[]
for x in range (0, N+1):
  for y in range (0, N+1-x):
    for z in range (0, N+1-x-y):
      if x + y +z == N and x*10000 + 5000*y + z*1000 == Y:
        number.append(x)
        number.append(y)
        number.append(z)
        
if len(number) >=3:
  print('{} {} {}'.format(number[0],number[1],number[2]))
else:
  print('-1 -1 -1')
  

### FIXED CODE ###

N, Y = map(int, input().split())
number =[]
for x in range (0, N+1):
  for y in range (0, N+1-x):
    z = N -x -y
    if z >= 0 and x*10000 + 5000*y + z*1000 == Y:
        number.append(x)
        number.append(y)
        number.append(z)

if len(number) >=3:
  print('{} {} {}'.format(number[0],number[1],number[2]))
else:
  print('-1 -1 -1')
### BUGGY CODE ###

n = int(input())
*A, = map(int, input().split())
# n = 6
# A = [8, 6, 9, 1, 2, 1]
# n = 4
# A = [1, 3, 4, 2]
A = [(a, i) for i, a in enumerate(A)]
A.sort(reverse=True)
DP = [[0 for r in range(n+1)] for l in range(n+1)]
for l in range(n):
    for r in range(n-l):
        a, i = A[l+r]
        DP[l+1][r] = max(DP[l+1][r], DP[l][r]+a*abs(i-l))
        DP[l][r+1] = max(DP[l][r+1], DP[l][r]+a*abs(i-(n-1-r)))
print(max([DP[l][n-l] for l in range(n)]))


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
# n = 6
# A = [8, 6, 9, 1, 2, 1]
# n = 4
# A = [1, 3, 4, 2]
A = [(a, i) for i, a in enumerate(A)]
A.sort(reverse=True)
DP = [[0 for r in range(n+1)] for l in range(n+1)]
for l in range(n):
    for r in range(n-l):
        a, i = A[l+r]
        DP[l+1][r] = max(DP[l+1][r], DP[l][r]+a*abs(i-l))
        DP[l][r+1] = max(DP[l][r+1], DP[l][r]+a*abs(i-(n-1-r)))
print(max([DP[l][n-l] for l in range(n)]))
### BUGGY CODE ###

#!python3

import sys
from functools import reduce
from operator import or_

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    N=len(S)
    lo, hi = 100, N//2
    md = 1
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = lo
    S1 = [None] * nn

    for i in range(nn):
        i1 = i * nn
        S1[i] = set(S[j] for j in range(i1, min(N, i1+nn)))

    ans = []
    rebuild = set()
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            i1 = i // nn
            S[i] = j
            rebuild.add(i1)
        elif cmd == "2":
            j = int(j)

            for i1 in rebuild:
                i2 = i1 * nn
                S1[i1] = set(S[k] for k in range(i2, min(N, i2+nn)))
            rebuild.clear()

            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            if ia < ja:
                ss = set()
                ss = reduce(or_, (S1[i1] for i1 in range(ia, ja)), ss)

                if ib > 0:
                    for i1 in range(i, i-ib+nn):
                        ss.add(S[i1])
                if jb > 0:
                    for i1 in range(ja*nn, j):
                        ss.add(S[i1])
            else:
                ss = set(S[k] for k in range(i, j))

            ans.append(len(ss))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys

from bisect import bisect, insort_left

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    S1 = [[] for i in range(26)]
    for i, c1 in enumerate(S):
        ci = ord(c1) - c0
        S1[ci].append(i)

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            c1 = ord(S[i]) - c0
            s1 = S1[c1]
            s1.pop(bisect(s1, i)-1)
            S[i] = j
            c1 = ord(j) - c0
            insort_left(S1[c1], i)
        elif cmd == "2":
            j = int(j) - 1
            num = 0

            for s1 in S1:
                ls = len(s1)
                k = bisect(s1, i-1, 0, ls)

                if k == ls:
                    continue
                if i <= s1[k] <= j:
                    num += 1

            ans.append(num)

    print(*ans, sep="\n")

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


def sieve(n):
    nums = [i+1 for i in range(2, n, 2) if (i+1) % 3 != 0 and (i+1) % 5 !=0] # リスト内包表記で3,5の倍数をはじく
    ans = [2,3,5] # 3,5は素数なので加えてしまう
    while nums[0] <= n**0.5:
        for i in range(nums[0]**2, nums[-1]+1, nums[0]):
            if i in nums: nums.remove(i)
            ans.append(nums.pop(0))
            ans += nums
    return ans

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

plis = sieve(max(7,min(A,B)))

ans = 1
for p in plis:
    if A%p +B%p ==0:
        ans += 1
        A = A//p
        B = B//p
        if min(A,B) == 1:
            break
print(ans)



### FIXED CODE ###


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

#素数列挙
def searchPrimeNum(N):
    max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum



#素因数分解(素数列挙が必要)
def pfact(N):
    plis = searchPrimeNum(int(N**0.5+1))
    ans = 1
    for p in plis:
        if N%p == 0:
            ans += 1
            N = N//p
        while N%p == 0:
            N = N//p
        if N == 1:
            break
    if N != 1:
        ans += 1
    return ans

#互除法(最大公約数)
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

print(pfact(gcd(A,B)))
### BUGGY CODE ###

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

def c(index):
    return index%N

total_rain = sum(A) // 2

rains = [0]*N
for m in range(N):
    one = total_rain
    for j in range(1, N-1, 2):
        one -= A[c(m+j)]
    rains[m] = one*2

ans = ""
for rain in rains:
    ans+=str(rain)
    ans+=" "

print(ans)

### FIXED CODE ###

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

total_rain = sum(A) // 2

one = total_rain
for j in range(1, N-1, 2):
    one -= A[j]
rain = one*2
ans = str(rain)
prerain = rain

for m in range(1, N):
    rain = (A[m-1] - prerain//2)*2
    ans+=" "
    ans+=str(rain)
    prerain = rain

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from collections import defaultdict


def solve():
    n = int(input())
    v = [int(i) for i in input().split()]
    d1 = defaultdict(int)
    d2 = defaultdict(int)
    for i in range(n):
        if i % 2 == 0:
            d1[v[i]] += 1
        else:
            d2[v[i]] += 1
    rd1 = defaultdict(list)
    rd2 = defaultdict(list)
    for k, v in d1.items():
        rd1[v].append(k)
    for k, v in d2.items():
        rd2[v].append(k)
    a1 = [i for i in sorted(rd1.keys(), reverse=True)]
    a2 = [i for i in sorted(rd2.keys(), reverse=True)]
    ans = n
    la1 = len(a1) - 1
    la2 = len(a2) - 1
    for h in range(3):
        for i in range(3):
            aa1 = rd1[a1[min(h, la1)]]
            aa2 = rd2[a2[min(i, la2)]]
            for j in aa1:
                for k in aa2:
                    if j != k:
                        ans = min(
                            ans, (n // 2) - a1[min(h, la1)] + (n // 2) - a2[min(i, la2)])
                    else:
                        ans = min(ans, (n // 2) - a1[min(h, la1)] + (n // 2) - a2[min(i, la2)]
                                  + min(a1[min(h, la1)], a2[min(i, la2)]))
    print(ans)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from collections import defaultdict


def solve():
    n = int(input())
    v = [int(i) for i in input().split()]
    d1 = defaultdict(int)
    d2 = defaultdict(int)
    for i in range(n):
        if i % 2 == 0:
            d1[v[i]] += 1
        else:
            d2[v[i]] += 1
    rd1 = defaultdict(list)
    rd2 = defaultdict(list)
    for k, v in d1.items():
        rd1[v].append(k)
    for k, v in d2.items():
        rd2[v].append(k)
    a1 = [i for i in sorted(rd1.keys(), reverse=True)]
    a2 = [i for i in sorted(rd2.keys(), reverse=True)]
    ans = n
    la1 = len(a1) - 1
    la2 = len(a2) - 1
    for h in range(3):
        for i in range(3):
            aa1 = rd1[a1[min(h, la1)]]
            aa2 = rd2[a2[min(i, la2)]]
            s1 = set(aa1)
            s2 = set(aa2)
            if len(s1) > 1 or len(s2) > 1 or (s1 - s2) or (s2 - s1):
                ans = min(
                    ans, (n // 2) - a1[min(h, la1)] + (n // 2) - a2[min(i, la2)])
            else:
                ans = min(ans, (n // 2) - a1[min(h, la1)] + (n // 2) - a2[min(i, la2)]
                          + min(a1[min(h, la1)], a2[min(i, la2)]))
    print(ans)


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

#intの場合
N = int(input()) #ここで標準入力

#List にしたい時
#intの場合
huga = list(map(int, input().split()))
ans = 1
for number in huga:
    ans = ans * number

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

### FIXED CODE ###

#intの場合
N = int(input()) #ここで標準入力

#List にしたい時
#intの場合
huga = list(map(int, input().split()))
if 0 in huga:
    print(0)
else:
    ans = 1
    flg = 0
    for number in huga:
        ans = ans * number
        if ans > 10**18:
            flg = 1
            break
    if flg == 0:
        print(ans)
    else:
        print('-1')
### BUGGY CODE ###

from collections import Counter
S = input()[::-1]
cur = 0
mods = Counter()
mods[0] += 1
for i,d in enumerate(S):
  cur += int(d) * 10**i
  mods[cur%2019] += 1

res = 0
for k,v in mods.items():
  res += (v * (v-1) // 2)

print(res)

### FIXED CODE ###

from collections import Counter
S = input()[::-1]
MOD = 2019
X = [0]
for i, s in enumerate(S):
  X.append((X[-1] + int(s)*pow(10,i,MOD)) % MOD)

C = Counter(X)
res = 0
for v in C.values():
  res += v*(v-1) // 2

print(res)
### BUGGY CODE ###

x,y,z,k=map(int, input().split())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
c=list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

sum_ab=[]

for i in a:
    for j in b:
      sum_ab.append(i+j)

sum_ab.sort(reverse=True)
sum_ab=sum_ab[:min(k,x*y)]

sum_abc=[]
for i in c:
    for j in sum_ab:
      sum_abc.append(i+j)

sum_abc.sort(reverse=True)
for i in range(k):
    print(sum_abc[i])

### FIXED CODE ###

x,y,z,k=map(int, input().split())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
c=list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

t=[]

for i in a:
    for j in b:
      t.append(i+j)

t.sort(reverse=True)
t=t[:min(k,x*y)]

ans=[]
for i in c:
    for j in t:
      ans.append(i+j)

ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

S = input()
N = len(S)
K = int(input())

S1 = {}
for i, s in enumerate(S):
    if not s in S1.keys():
        S1[s] = [i]
    else:
        S1[s].append(i)
alp = sorted(list(S1.keys()))

c = 0
for a in alp:
    aset = set()
    inds = S1[a]
    for d in inds:
        for i in range(N-d+1):
            aset.add(S[d:d+i])
    if len(aset)-1 >= K-c:
        break
    c += len(aset)-1


while True:
    for i, a in enumerate(aset):
        if i == 0:
            min = a
            continue
        if a < min:
            min = a
    aset.discard(min)
    if min == '':
        continue
    c += 1
    if c >= K:
        ans = min
        break

print(ans)


### FIXED CODE ###

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

    S1 = {}
    for i, s in enumerate(S):
        if not s in S1.keys():
            S1[s] = [i]
        else:
            S1[s].append(i)
    alp = sorted(list(S1.keys()))

    c = 0
    for a in alp:
        aset = set()
        inds = S1[a]
        for d in inds:
            up = min(N-d+1, K+1)
            for i in range(up):
                aset.add(S[d:d+i])
        L = len(aset)-1
        if L >= K-c:
            break
        c += L

    for _ in range(10):
        M = '何だこれはもうやめてくれよ'
        for a in aset:
            if a < M:
                M = a
        aset.discard(M)
        if M == '':
            continue
        c += 1
        if c >= K:
            ans = M
            break

    print(ans)



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

## coding: UTF-8
N,M = map(int,input().split())
H = list(map(int,input().split()))

path = []
for i in range(M):
    path.append(list(map(int,input().split())))

l = [] 
for i in range(N):
    l.append([0] * N + [H[i]])



highest = [0] + [1] * N
#print(highest)
#print(H)
for i in range(M):
    #print('path[i][0] = {}, path[i][1] = {}'.format(path[i][0], path[i][1]))
    #print('H[path[i][0]-1]:{}, H[path[i][1]-1]:{}'.format(H[path[i][0]-1], H[path[i][1]-1]))
    p = path[i][1]-1
    q = path[i][0]-1
    x = H[p]
    y = H[q]
    if( x >= y ):
        #print('deny at {}'.format(path[i][0]))
        highest[q+1] = 0
    if(  x <= y  ):
        #print('deny at {}'.format(path[i][1]))
        highest[p+1] = 0
    #print('highest:{}'.format(highest))

print(sum(highest))

'''
for i in range(M):
    print('path[i][0] = Ai = {}, path[i][1] = Bi = {}'.format(path[i][0], path[i][1]))
    l[ path[i][0]-1 ][ path[i][1]-1 ] = H[path[i][1]-1]
    l[ path[i][1]-1 ][ path[i][0]-1 ] = H[path[i][0]-1]
    print(l)
'''



'''
m_neigh = []
for i in range(N):
    print(l[i][:N])
    m_neigh.append(  max(l[i][:N] )  )
    print(m_neigh)
'''
'''
cnt = 0
for i in range(N):
    
'''

### FIXED CODE ###

## coding: UTF-8
N,M = map(int,input().split())
H = list(map(int,input().split()))

'''
path = []
for i in range(M):
    path.append(list(map(int,input().split())))
'''
path = [list(map(int,input().split())) for i in range(M)]  # 二次元配列入力　二次元マップみたいな入力のとき

'''
l = [] 
for i in range(N):
    l.append([0] * N + [H[i]])
'''


highest = [0] + [1] * N
#print(highest)
#print(H)
for i in range(M):
    #print('path[i][0] = {}, path[i][1] = {}'.format(path[i][0], path[i][1]))
    #print('H[path[i][0]-1]:{}, H[path[i][1]-1]:{}'.format(H[path[i][0]-1], H[path[i][1]-1]))
    pa = path[i]
    p = pa[1]-1
    q = pa[0]-1
    x = H[p]
    y = H[q]
    if( x >= y ):
        #print('deny at {}'.format(path[i][0]))
        highest[q+1] = 0
    if(  x <= y  ):
        #print('deny at {}'.format(path[i][1]))
        highest[p+1] = 0
    #print('highest:{}'.format(highest))

print(sum(highest))

'''
for i in range(M):
    print('path[i][0] = Ai = {}, path[i][1] = Bi = {}'.format(path[i][0], path[i][1]))
    l[ path[i][0]-1 ][ path[i][1]-1 ] = H[path[i][1]-1]
    l[ path[i][1]-1 ][ path[i][0]-1 ] = H[path[i][0]-1]
    print(l)
'''



'''
m_neigh = []
for i in range(N):
    print(l[i][:N])
    m_neigh.append(  max(l[i][:N] )  )
    print(m_neigh)
'''
'''
cnt = 0
for i in range(N):
    
'''
### BUGGY CODE ###

import re
 
S = input()
ans = 0
while True:
    S, n = re.subn('BW', 'WB', S)
    if n == 0:
        break
    ans += n
 
print(ans)

### FIXED CODE ###

S = input()

b_count = 0
ans = 0

for pos in range(len(S)):
    if S[pos] == 'B':
        b_count += 1
    else:
        ans += b_count

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

S = input()
len_s = len(S)
while(True):
    S = S.replace("01", "")
    S = S.replace("10", "")
    S = S.replace("01", "")
    S = S.replace("10", "")
    S = S.replace("01", "")
    S = S.replace("10", "")
    S = S.replace("01", "")
    S = S.replace("10", "")
    S = S.replace("01", "")
    S = S.replace("10", "")
    if not "01" in S:
        if not "10" in S:
            break
print(len_s - len(S))

### FIXED CODE ###

S = input()
if len(S) == 1:
    print(0)
else:
    print(min(S.count('0'), S.count('1')) * 2)
### BUGGY CODE ###

n = input()
s = 0
for x in n:
    s += int(n)
if s % 9 == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N = int(input())
if N % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from collections import deque
S = deque(input())
Q = int(input())
for i in range(Q):
    TFC = input()
    if TFC == "1":
        S.reverse()
    else:
        if TFC[:3]== "2 1":
            S.appendleft(TFC[4])
        else:
            S.append(TFC[4])
print("".join([i for i in S]))

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
cnt = 1
num = 0
for i in range(Q):
    TFC = input()
    if TFC == "1":
        cnt *= -1
        num += 1
    else:
        if TFC[:3]== "2 1":
            if cnt ==1:
                S.appendleft(TFC[4])
            else:
                S.append(TFC[4])
        else:
            if cnt ==1:
                S.append(TFC[4])
            else:
                S.appendleft(TFC[4])
if num % 2 ==1:
    print(("".join(reversed([i for i in S]))))
else:
    print(("".join([i for i in S])))
### BUGGY CODE ###

S = str(input())
i, ans = (0, 0)
while i<len(S)-1:
    if S[i]!=S[i+1]:
        S = S[:i]+S[i+2:] if i+2<len(S) else S[:i]
        ans += 2
        i-=1
    else:
        i+=1
print(ans)

### FIXED CODE ###

from collections import deque
sin = input()
queue = deque(maxlen=len(sin))
for s in sin:
    if len(queue)>0 and queue[-1] != s:
        queue.pop()
    else:
        queue.append(s)
#print("".join(arr))
print(len(sin)-len(queue))
### BUGGY CODE ###

from collections import deque

s = input()
a = deque(s)

q = int(input())

for i in range(q):
    inp = input()
    if inp == '1':
        a.reverse()
    else:
        if inp.split()[1] == '1':
            a.appendleft(inp.split()[2])
        else:
            a.append(inp.split()[2])
            
print(''.join(a))


### FIXED CODE ###

from collections import deque

s = input()
d = deque(s)
q = int(input())

rev = False

for i in range(q):
    inp = input()
    if inp == '1':
        rev = True if rev == False else False
    else:
        n = inp.split()[1]
        t = inp.split()[2]
        if n == '1':
            d.append(t) if rev == True else d.appendleft(t)
        else:
            d.appendleft(t) if rev == True else d.append(t)

if rev == True:
    d.reverse()

print(''.join(d))
### BUGGY CODE ###

import sys
from collections import defaultdict
readline = sys.stdin.readline
N, = map(int, readline().split())
def con(ll,E):
    rs = []
    for u, v in zip(ll,ll[1:]):
        u, v = sorted([u,v])
        rs.append(E[(u,v)])
    return set(rs)

def process():
    G = [[] for _ in range(N+1)]
    E = dict()
    for i in range(N-1):
        a, b = sorted(map(int, readline().split()))
        G[a].append(b)
        G[b].append(a)
        E[(a,b)] = i

    M, = map(int, readline().split())
    qes = dict()
    for _ in range(M):
        u, v = sorted(map(int, readline().split()))
        if u not in qes:
            qes[u] = list()
        qes[u].append(v)
    dep = []
    for i in qes:
        ms = qes[i]
        path = []
        stack = [i]
        vs = set([i])
        while stack:
            v = stack.pop()
            if v > 0:
                vs.add(v)
#                parent = path[-1]
                path.append(v)
                for u in G[v]:
                    if u in vs:
                        continue
                    if u in ms:
                        dep.append(con(path+[u],E))
                    stack += [-v, u]
            else:
                path.pop()
    r = 0
    for i in range(1,2**M):
        t = 0
        ns = set()
#        lns = 
        for j in range(M):
            if i % 2:
                ns = ns | dep[j]
                t += 1
            i = i>>1
        xx = (1 if t%2 else -1)*2**(N-1-len(ns))
        r += xx
    print(2**(N-1)-r)
if __name__ == '__main__':
    process()


### FIXED CODE ###

import sys
from collections import defaultdict
readline = sys.stdin.readline
N, = map(int, readline().split())
def con(ll,E):
    r = 0
    for u, v in zip(ll,ll[1:]):
        u, v = sorted([u,v])
        r += 1<<E[(u,v)]
    return r

def process():
    G = [[] for _ in range(N+1)]
    E = dict()
    for i in range(N-1):
        a, b = sorted(map(int, readline().split()))
        G[a].append(b)
        G[b].append(a)
        E[(a,b)] = i

    M, = map(int, readline().split())
    qes = dict()
    for _ in range(M):
        u, v = sorted(map(int, readline().split()))
        if u not in qes:
            qes[u] = list()
        qes[u].append(v)
    dep = []
    for i in qes:
        ms = qes[i]
        path = []
        stack = [i]
        vs = set([i])
        while stack:
            v = stack.pop()
            if v > 0:
                vs.add(v)
#                parent = path[-1]
                path.append(v)
                for u in G[v]:
                    if u in vs:
                        continue
                    if u in ms:
                        dep.append(con(path+[u],E))
                    stack += [-v, u]
            else:
                path.pop()
    r = 0
    for i in range(1,2**M):
        t = 0
        ns = 0
#        lns = 
        for j in range(M):
            if i % 2:
                ns = ns | dep[j]
                t += 1
            i = i>>1
        xx = (1 if t%2 else -1)*2**(N-1-bin(ns).count("1"))
        r += xx
    print(2**(N-1)-r)
if __name__ == '__main__':
    process()
### BUGGY CODE ###



def p(k,w,maxP):
    count = 1
    tmpList = []
    mP = 0
    for x in w:
        if sum(tmpList)+x <= maxP:
            tmpList.append(x)
            mP = max(sum(tmpList),mP)
        else:
            count += 1
            tmpList = []
            tmpList.append(x)
    if count > k:
        result = False
    else:
        result = True

    return result, count, mP

n,k = map(int,input().split())


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = 1000000000
rangeMin = max(w)

while _:
    rangeMid = (rangeMax + rangeMin)//2

    if p(k,w,rangeMid)[0] == False and p(k,w,rangeMid+1)[0] == False:
        rangeMin = rangeMid
    elif p(k,w,rangeMid)[0] == True and p(k,w,rangeMid+1)[0] == True:
        rangeMax = rangeMid
    else:
        break

print(p(k,w,rangeMid+1)[2])

### FIXED CODE ###



def p(k,w,maxP):
    count = 1
    tmpWeight = 0
    for x in w:
        if tmpWeight+x <= maxP:
            tmpWeight += x
        else:
            count += 1
            if count > k :
                return False
            tmpWeight = x
    

    return True




n,k = map(int,input().split())


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = sum(w)
rangeMin = max(w)
rangeMid = 0
while rangeMin < rangeMax:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == True:
        rangeMax = rangeMid
    else:
        rangeMid += 1
        rangeMin = rangeMid

print(rangeMid)