Painters Partition | Binary Search

import sys,os,io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
#sorted_x = sorted(x.items(), key=lambda kv: kv[1]) 
# returns list
#{k: v for k, v in sorted(x.items(), key=lambda item: item[1])}
# returns dict
#input = sys.stdin.readline
# Both + and ^ ops changes parity if one of the operand is odd 
from collections import defaultdict, Counter,deque
mod = 10 ** 9 + 7
def yn(f): 
	print("NO" if f else "YES")
import math
import bisect
def ok(numb,k):
    i=0 
    summ=0 
    c=1 
    while(i<len(l)):
        if l[i]>numb:
            return False
        if summ+l[i]>numb:
            c+=1 
            summ=l[i] 
        else:
            summ+=l[i]
        i+=1 
    if c<=k:
        return True 
    return False
    
t=int(input())
for a0 in range(t):
    n,k=[int(i) for i in input().split()]
    l=[int(i) for i in input().split()]
    #print(l,len(l))
    #z=len(l)
    le=0 
    r=(10**6)+5 
    while(le<r):
        mid=(le+r+1)//2 
        if(ok(mid,k)):
            r=mid-1
        else:
            le=mid
    print(r+1)