CodeEff/ECCO huggingface dataset:
# Original solution
def main():
  #points = [[False for i in range(5001)] for j in range(5001)]
  while True:
    n = int(eval(input()))
    if not n:
      break
    ps = []
    dic = {}

    for i in range(n):
      x, y = list(map(int,input().split()))
      dic[(x, y)] = 1;
      #points[x][y] = True
      ps.append((x,y))
  
    ans = 0
  
    for i in range(n):
      for j in range(n):
        p1 = ps[i]
        p2 = ps[j]
        vx = p2[0] - p1[0]
        vy = p2[1] - p1[1]
        #if  0 <= p1[0] + vy <= 5000 and 0 <= p1[1] - vx <= 5000 and 0 <= p2[0] + vy <= 5000 and 0 <= p2[1] - vx <= 5000:
        #  if  points[p1[0] + vy][p1[1] - vx] and points[p2[0] + vy][p2[1] - vx]:
        if (p1[0] + vy, p1[1] - vx) in dic and (p2[0] + vy, p2[1] - vx) in dic:
          ans = max(ans, vx ** 2 + vy ** 2)
    
    #for p in ps:
    #  points[p[0]][p[1]] = False

    print(ans)
main()  





# Optimized solution
def main():
  while True:
    n = int(eval(input()))
    if not n:
      break
    ps = []
    dic = {}

    for i in range(n):
      x, y = list(map(int,input().split()))
      dic[(x, y)] = 1;
      ps.append((x,y))
  
    ans = 0
  
    for i in range(n):
      for j in range(n):
        p1 = ps[i]
        p2 = ps[j]
        p1x = p1[0]
        p1y = p1[1]
        p2x = p2[0]
        p2y = p2[1]
        vx = p2x - p1x
        vy = p2y - p1y
        if (p1x + vy, p1y - vx) in dic and (p2x + vy, p2y - vx) in dic:
          ans = max(ans, vx ** 2 + vy ** 2)
    

    print(ans)
main()
# Original solution
def main():
  while True:
    n = int(eval(input()))
    if not n:
      break
    ps = []
    dic = {}

    for i in range(n):
      x, y = list(map(int,input().split()))
      dic[(x, y)] = 1;
      ps.append((x,y))
  
    ans = 0
  
    for i in range(n):
      for j in range(n):
        p1 = ps[i]
        p2 = ps[j]
        p1x = p1[0]
        p1y = p1[1]
        p2x = p2[0]
        p2y = p2[1]
        vx = p2x - p1x
        vy = p2y - p1y
        if (p1x + vy, p1y - vx) in dic and (p2x + vy, p2y - vx) in dic:
          ans = max(ans, vx ** 2 + vy ** 2)
    

    print(ans)
main()  





# Optimized solution
def main():
  while True:
    n = int(eval(input()))
    if not n:
      break
    ps = [list(map(int,input().split())) for i in range(n)]
    dic = set()
    for t in ps:
      dic.add((t[0],t[1]))
    ans = 0
  
    for i in range(n):
      for j in range(n):
        p1 = ps[i]
        p2 = ps[j]
        p1x = p1[0]
        p1y = p1[1]
        p2x = p2[0]
        p2y = p2[1]
        vx = p2x - p1x
        vy = p2y - p1y
        if (p1x + vy, p1y - vx) in dic and (p2x + vy, p2y - vx) in dic:
          ans = max(ans, vx ** 2 + vy ** 2)
    

    print(ans)
main()
# Original solution
import itertools
while 1:
	n = eval(input())
	if n == 0: break
	xy = sorted([list(map(int,input().split())) for i in range(n)])
	dxy = [[xy1[0]-xy2[0],xy1[1]-xy2[1]] for xy1,xy2 in itertools.combinations(xy,2)]
	for i in range(len(dxy)-1,-1,):
		if dxy.count(dxy[i]) < 2: del dxy[i]
	dxy = sorted(dxy, key = lambda d:d[0]**2 + d[1]**2, reverse = True) 
	for dx,dy in dxy:
		if dxy.count([dy,-dx]) > 1 or dxy.count([-dy,-dx]) > 1:
			print(dx**2 + dy**2)
			break
	else:
		print(0)

# Optimized solution
p = 100
while 1:
	n = eval(input())
	if n == 0: break
	xy = sorted([list(map(int,input().split())) for i in range(n)])
	S = set(map(tuple,xy))
	ans = 0
	for i in range(n):
		x1,y1 = xy[i]
		xy = xy[:i] + sorted(xy[i:], key = lambda XY:(XY[0]-x1)**2 + (XY[1]-y1)**2)
		cur = 0
		for j in range(n-1,i,-1):
			x2,y2 = xy[j]
			a = (x2-y2+y1,y2+x2-x1)
			b = (x1-y2+y1,y1+x2-x1)
			if a in S and b in S:
				cur = (x1-x2)**2 + (y1-y2)**2
				break
		ans = max(ans,cur)
	print(ans)
# Original solution
p = 100
while 1:
	n = eval(input())
	if n == 0: break
	xy = sorted([list(map(int,input().split())) for i in range(n)])
	S = set(map(tuple,xy))
	ans = 0
	for i in range(n):
		x1,y1 = xy[i]
		xy = xy[:i] + sorted(xy[i:], key = lambda XY:(XY[0]-x1)**2 + (XY[1]-y1)**2)
		cur = 0
		for j in range(n-1,i,-1):
			x2,y2 = xy[j]
			a = (x2-y2+y1,y2+x2-x1)
			b = (x1-y2+y1,y1+x2-x1)
			if a in S and b in S:
				cur = (x1-x2)**2 + (y1-y2)**2
				break
		ans = max(ans,cur)
	print(ans)

# Optimized solution
while 1:
	n = eval(input())
	if n == 0: break
	xy = [list(map(int,input().split())) for i in range(n)]
	S = set(map(tuple,xy))
	ans = 0
	for i in range(n):
		x1,y1 = xy[i]
		for j in range(n-1,i,-1):
			x2,y2 = xy[j]
			a = (x2-y2+y1,y2+x2-x1)
			b = (x1-y2+y1,y1+x2-x1)
			if a in S and b in S:
				ans = max(ans,(x1-x2)**2 + (y1-y2)**2)
	print(ans)
# Original solution
def dot(c1, c2):
    return c1.real * c2.real + c1.imag * c2.imag

def cross(c1, c2):
    return c1.real * c2.imag - c1.imag * c2.real

def string_to_complex(s):
    x, y = list(map(int, s.split()))
    return x + y * 1j

def contains(polygon, point):
    up = False
    down = False
    start_point = polygon[0]
    for p in polygon[::-1]:
        if start_point.imag > p.imag:
            up = True
            break
        elif start_point.imag < p.imag:
            down = True
            break
    flag = False
    for v1, v2 in zip(polygon[0:], polygon[1:]):
        a = v1 - point
        b = v2 - point
        if cross(a, b) == 0 and dot(a, b) <= 0:
            return 1
        if a.imag < b.imag:
            if a.imag < 0 or (a.imag == 0 and up):
                if b.imag > 0 and cross(a, b) > 0:
                    flag = not flag
            up = True
            down = False
        elif a.imag > b.imag:
            if a.imag > 0 or (a.imag == 0 and down):
                if b.imag < 0 and cross(a, b) < 0:
                    flag = not flag
            up = False
            down = True
    if flag:
        return 2
    else:
        return 0

import sys

file_input = sys.stdin

n = int(file_input.readline())

polygon = [string_to_complex(file_input.readline()) for i in range(n)]
polygon.append(polygon[0])

q = int(file_input.readline())

for line in file_input:
    t = string_to_complex(line)
    print((contains(polygon, t)))

# Optimized solution
def dot(c1, c2):
    return c1.real * c2.real + c1.imag * c2.imag

def cross(c1, c2):
    return c1.real * c2.imag - c1.imag * c2.real

def string_to_complex(s):
    x, y = list(map(int, s.split()))
    return x + y * 1j

def contains(polygon, point):
    flag = False
    for v1, v2 in zip(polygon[0:], polygon[1:]):
        a = v1 - point
        b = v2 - point
        if a.imag > b.imag:
            a, b = b, a
        cross_ab = cross(a, b)
        if a.imag <= 0 and b.imag > 0 and cross_ab > 0:
            flag = not flag
        if cross_ab == 0 and dot(a, b) <= 0:
            return 1
    if flag:
        return 2
    else:
        return 0

import sys

file_input = sys.stdin

n = int(file_input.readline())

polygon = [string_to_complex(file_input.readline()) for i in range(n)]
polygon.append(polygon[0])

q = int(file_input.readline())

for line in file_input:
    t = string_to_complex(line)
    print((contains(polygon, t)))
# Original solution
def dot(c1, c2):
    return c1.real * c2.real + c1.imag * c2.imag

def cross(c1, c2):
    return c1.real * c2.imag - c1.imag * c2.real

def string_to_complex(s):
    x, y = list(map(int, s.split()))
    return x + y * 1j

def contains(polygon, point):
    flag = False
    for v1, v2 in zip(polygon[0:], polygon[1:]):
        a = v1 - point
        b = v2 - point
        if a.imag > b.imag:
            a, b = b, a
        cross_ab = cross(a, b)
        if a.imag <= 0 and b.imag > 0 and cross_ab > 0:
            flag = not flag
        if cross_ab == 0 and dot(a, b) <= 0:
            return 1
    if flag:
        return 2
    else:
        return 0

import sys

file_input = sys.stdin

n = int(file_input.readline())

polygon = [string_to_complex(file_input.readline()) for i in range(n)]
polygon.append(polygon[0])

q = int(file_input.readline())

for line in file_input:
    t = string_to_complex(line)
    print((contains(polygon, t)))

# Optimized solution
def dot(c1, c2):
    return c1.real * c2.real + c1.imag * c2.imag

def cross(c1, c2):
    return c1.real * c2.imag - c1.imag * c2.real

def string_to_complex(s):
    x, y = list(map(int, s.split()))
    return x + y * 1j

def contains(polygon, point):
    flag = False
    for v1, v2 in zip(polygon[0:], polygon[1:]):
        a = v1 - point
        b = v2 - point
        if a.imag > b.imag:
            a, b = b, a
        cross_ab = cross(a, b)
        if cross_ab == 0 and dot(a, b) <= 0:
            return 1
        if a.imag <= 0 and b.imag > 0 and cross_ab > 0:
            flag = not flag
    if flag:
        return 2
    else:
        return 0

import sys

file_input = sys.stdin

n = int(file_input.readline())

polygon = [string_to_complex(file_input.readline()) for i in range(n)]
polygon.append(polygon[0])

q = int(file_input.readline())

for line in file_input:
    t = string_to_complex(line)
    print((contains(polygon, t)))
# Original solution
from math import atan2
n = eval(input())
p = [list(map(int, input().split())) for i in range(n)]
for t in range(eval(input())):
    x, y = list(map(int, input().split()))

    inline = 0
    theta = 0.
    for i in range(n):
        x0 = p[i-1][0] - x
        y0 = p[i-1][1] - y
        x1 = p[i][0] - x
        y1 = p[i][1] - y

        if x0*y1 == y0*x1 and x0*x1+y0*y1 <= 0:
            inline = 1
            break
        theta += atan2(x0*y1-y0*x1, x0*x1+y0*y1)
    if inline:
        print(1)
    elif theta > 1:
        print(2)
    else:
        print(0)

# Optimized solution
def inside_polygon(p0, qs):
    cnt = 0
    L = len(qs)
    x, y = p0
    for i in range(L):
        x0, y0 = qs[i-1]; x1, y1 = qs[i]
        x0 -= x; y0 -= y
        x1 -= x; y1 -= y

        cv = x0*x1 + y0*y1
        sv = x0*y1 - x1*y0
        if sv == 0 and cv <= 0:
            return 1

        if not y0 < y1:
            x0, x1 = x1, x0
            y0, y1 = y1, y0

        if y0 <= 0 < y1 and x0*(y1 - y0) > y0*(x1 - x0):
            cnt += 1
    return 2 if cnt % 2 == 1 else 0

def solve():
    N = int(eval(input()))
    qs = [list(map(int, input().split())) for i in range(N)]

    Q = int(eval(input()))
    for i in range(Q):
        *p0, = list(map(int, input().split()))
        print((inside_polygon(p0, qs)))
solve()
# Original solution
#coding:utf-8
   
n, k = list(map(int, input().split()))
backList = []
for i in range(n):
    backList.append(int(eval(input())))

def capa(p,k):
    cnt = 0
    pcopy = p
    num = 0
    for back in backList:
        if back > p:
            break
        if back <= pcopy:
            pcopy -= back
            cnt += 1
            continue
        elif back > pcopy:
            if num == k-1:
                return cnt
            pcopy = p - back
            cnt += 1
            num += 1          
    return cnt


p_min = 0
p_max = 100000 * 10000
def biSearch(p_min, p_max):
    p = p_max - p_min
    if p_min == p_max:
        return p_min
    if p % 2 == 0:
        p = int(p/2)
    else:
        p = int((p+1)/2)
    v = capa(p,k)
    if v < n:
        p_min = p_min + p
    else:
        p_max = p_min + p

    return biSearch(p_min, p_max)
            

p = biSearch(p_min, p_max)
n_init = n
while n_init <= n:
    p -= 1
    n = capa(p,k)

print((p+1))



# Optimized solution
#coding:utf-8
   
n, k = list(map(int, input().split()))
backList = []
for i in range(n):
    backList.append(int(eval(input())))

def capa(p,k):
    cnt = 0
    pcopy = p
    num = 0
    for back in backList:
        if back > p:
            break
        if back <= pcopy:
            pcopy -= back
            cnt += 1
            continue
        elif back > pcopy:
            if num == k-1:
                return cnt
            pcopy = p - back
            cnt += 1
            num += 1          
    return cnt


p_min = 0
p_max = 100000 * 10000
def biSearch(p_min, p_max):
    p = p_max - p_min
    if p_max - p_min <= 1:
        return p_max
    if p % 2 == 0:
        c = p_min + int(p/2)
    else:
        c = p_min + int((p+1)/2)
    v = capa(c,k)
    if v < n:
        p_min = c
    else:
        p_max = c

    return biSearch(p_min, p_max)
            

p = biSearch(p_min, p_max)
n_init = n
while n_init <= n:
    p -= 1
    n = capa(p,k)

print((p+1))
# Original solution
def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    heaviest_baggage = max(baggage)
    average_capacity = sum(baggage) // truck_num
    capacity = max(heaviest_baggage, average_capacity)
    while carriable_baggage(baggage, baggage_num, capacity, truck_num) < baggage_num:
        capacity += 1
    return capacity


import sys

baggage_num, truck_num = list(map(int, sys.stdin.readline().split()))

baggage = list(map(int, sys.stdin))

capacity = min_capacity(baggage, baggage_num, truck_num)

print(capacity)

# Optimized solution
def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    left = 0
    right = 10000 * baggage_num
    while right - left > 1:
        mid = (left + right) // 2
        v = carriable_baggage(baggage, baggage_num, mid, truck_num)
        if v >= baggage_num:
            right = mid;
        else:
            left = mid
    return right


import sys

n, k = list(map(int, sys.stdin.readline().split()))

T = list(map(int, sys.stdin))

P = min_capacity(T, n, k)

print(P)
# Original solution
def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    left = 0
    right = 10000 * baggage_num
    while right - left > 1:
        mid = (left + right) // 2
        v = carriable_baggage(baggage, baggage_num, mid, truck_num)
        if v >= baggage_num:
            right = mid;
        else:
            left = mid
    return right


import sys

n, k = list(map(int, sys.stdin.readline().split()))

T = list(map(int, sys.stdin))

P = min_capacity(T, n, k)

print(P)

# Optimized solution
def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    heaviest_baggage = max(baggage)
    left = 0
    right = heaviest_baggage * baggage_num
    while right - left > 1:
        mid = (left + right) // 2
        v = carriable_baggage(baggage, baggage_num, mid, truck_num)
        if v >= baggage_num:
            right = mid;
        else:
            left = mid
    return right


import sys

n, k = list(map(int, sys.stdin.readline().split()))

T = list(map(int, sys.stdin))

P = min_capacity(T, n, k)

print(P)
# Original solution
def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    left = 0
    right = max(baggage) * baggage_num
    while right - left > 1:
        mid = (left + right) // 2
        v = carriable_baggage(baggage, baggage_num, mid, truck_num)
        if v >= baggage_num:
            right = mid;
        else:
            left = mid
    return right


import sys

n, k = list(map(int, sys.stdin.readline().split()))

T = list(map(int, sys.stdin))

P = min_capacity(T, n, k)

print(P)

# Optimized solution
def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    left = 0
    right = 10000 * baggage_num
    while right - left > 1:
        mid = (left + right) // 2
        v = carriable_baggage(baggage, baggage_num, mid, truck_num)
        if v >= baggage_num:
            right = mid;
        else:
            left = mid
    return right


import sys

n, k = list(map(int, sys.stdin.readline().split()))

T = list(map(int, sys.stdin))

P = min_capacity(T, n, k)

print(P)
# Original solution
import sys
def f(P):
 i=0
 for _ in[0]*k:
  s=0
  while s+w[i]<=P:
   s+=w[i];i+=1
   if i==n: return n
 return i
n,k=list(map(int,input().split()))
w=list(map(int,sys.stdin.read().splitlines()))
l=0;r=n*100000
while r-l>1:
 m=(l+r)//2
 if f(m)>=n:r=m
 else:l=m
print(r)


# Optimized solution
import sys
def f(P):
 i=0
 for _ in[0]*k:
  s=0
  while s+w[i]<=P:
   s+=w[i];i+=1
   if i==n: return n
 return i
n,k=list(map(int,input().split()))
w=list(map(int,sys.stdin.read().splitlines()))
l=0;r=sum(w)
while r-l>1:
 m=(l+r)//2
 if f(m)>=n:r=m
 else:l=m
print(r)
# Original solution
import sys
def f(P):
 i=0
 for _ in[0]*k:
  s=0
  while s+w[i]<=P:
   s+=w[i];i+=1
   if i==n: return n
 return i
n,k=list(map(int,input().split()))
w=list(map(int,sys.stdin.read().splitlines()))
l=0;r=sum(w)
while r-l>1:
 m=(l+r)//2
 if f(m)>=n:r=m
 else:l=m
print(r)


# Optimized solution
import sys
def f(P):
 i=0
 for _ in[0]*k:
  s=0
  while s+w[i]<=P:
   s+=w[i];i+=1
   if i==n: return n
 return i
n,k=list(map(int,input().split()))
w=list(map(int,sys.stdin.readlines()))
l=0;r=sum(w)
while r-l>1:
 m=(l+r)//2
 if f(m)>=n:r=m
 else:l=m
print(r)
# Original solution
import sys
n,k=list(map(int,input().split()))
w=list(map(int,sys.stdin.readlines()))
def f():
 i=0
 for _ in[0]*k:
  s=0
  while s+w[i]<=m:
   s+=w[i];i+=1
   if i==n:return n
 return i
l,r=max(w),sum(w)
while l<r:
 m=(l+r)//2
 if f()>=n:r=m
 else:l=m+1
print(r)


# Optimized solution
import sys
def s():
 n,k=list(map(int,input().split()))
 w=list(map(int,sys.stdin.readlines()))
 def f():
  c=t=0
  for j in w:
   t+=j
   if t>m:
    t=j
    c+=1
    if c>=k:return 0
  return 1
 l,r=max(w),sum(w)
 while l<r:
  m=(l+r)//2
  if f():r=m
  else:l=m+1
 print(r)
if'__main__'==__name__:s()
# Original solution
num, track = [int(x) for x in input().split()]
hoge_l = list()
for _ in range(num):
    hoge_l.append(int(eval(input())))
hoge_i = sum(hoge_l)
if hoge_i % track == 0:
    hoge_i = hoge_i // track
else:
    hoge_i = hoge_i // track + 1

while True:
    tmp = 0
    c = 1
    for v in hoge_l:
        tmp += v
        if tmp > hoge_i:
            c += 1
            tmp = 0
            tmp += v
    if c == track:
        break
    elif c > track:
        hoge_i += 1
max_num = max(hoge_l)
if max_num > hoge_i:
    hoge_i = max_num
print (hoge_i)


# Optimized solution
def imas(hoge_l, p, track):
    s_weights = 0
    now_track = 1
    for val in hoge_l:
        s_weights += val
        if s_weights > p:
            s_weights = val
            now_track += 1
        if now_track > track:
            return False
    return True

num, track = [int(x) for x in input().split()]
hoge_l = list()
for _ in range(num):
    hoge_l.append(int(eval(input())))
left = 0
right = 100000 * 10000

while left < right :
    mid = (right + left) // 2
    if imas(hoge_l, mid, track):
        right = mid 
    else:
        left = mid + 1
        
max_num = max(hoge_l)
if max_num > right:
    right = max_num
print (right)
# Original solution


global N,K
global ws

def check(max_p):
    track=0
    now=0
    for i in range (N):
        if(ws[i]>max_p):return False
        if(now+ws[i]>max_p):
            track+=1
            now=ws[i]
        else:
            now+=ws[i]
    if now>0:
        track+=1
    if(track>K):
        return False
    else:
        return True

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

ans=0
now=0
ws=[]
for i in range(N):
    w=int(eval(input()))
    ws.append(w)

amin=0
amax=int(1E100)

while amin+1!=amax:
    amid=(amin+amax)//2
    if(check(amid)):
        amax=amid
    else:
        amin=amid
print(amax)
   

# Optimized solution


global N,K
global ws

def check(max_p):
    track=0
    now=0
    for i in range (N):
        if(ws[i]>max_p):return False
        if(now+ws[i]>max_p):
            track+=1
            now=ws[i]
        else:
            now+=ws[i]
    if now>0:
        track+=1
    if(track>K):
        return False
    else:
        return True

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

ans=0
now=0
ws=[]
for i in range(N):
    w=int(eval(input()))
    ws.append(w)

amin=0
amax=int(1E30)

while amin+1!=amax:
    amid=(amin+amax)//2
    if(check(amid)):
        amax=amid
    else:
        amin=amid
print(amax)
# Original solution
import math
n, k = list(map(int, input().split()))
a = [int(eval(input())) for _ in [None]*n]

lb = max(a)
ub = lb * n

while True:
    mid = (ub+lb) // 2
    remain = k - 1
    cw = 0
    for w in a:
        cw += w
        if cw > mid:
            remain -= 1
            cw = w
        if remain < 0:
            break
    if remain < 0:
        if lb == mid:
            print((lb+1))
            break
        lb = mid
    else:
        if lb == mid:
            print(lb)
            break
        ub = mid

# Optimized solution
def solve():
    import sys
    n, k = list(map(int, input().split()))
    ws = tuple(map(int, sys.stdin))

    ok, ng = sum(ws), max(ws)-1

    while ok-ng > 1:
        mid = (ok+ng+1)//2
        current = 0
        count = 0
        for w in ws:
            if current + w > mid:
                current = w
                count += 1
            else:
                current += w
        if count < k:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == "__main__":
    solve()