CodeEff/ECCO huggingface dataset:
# Original solution
# https://atcoder.jp/contests/abc100/tasks/abc100_d

from itertools import product

N, M, *XYZ = list(map(int, open(0).read().split()))

P = tuple(product((1, -1), repeat=3))

A = [[] for _ in range(8)]
for x, y, z in zip(*[iter(XYZ)] * 3):
    for i, (a, b, c) in enumerate(P):
        A[i].append(a * x + b * y + c * z)

cand = []
for i in range(8):
    A[i].sort(reverse=True)
    cand.append(sum(A[i][:M]))

print((max(cand)))


# Optimized solution
N, M, *XYZ = list(map(int, open(0).read().split()))

A = [[] for _ in range(8)]
for x, y, z in zip(*[iter(XYZ)] * 3):
    A[0].append(sum((x, y, z)))
    A[1].append(sum((x, y, -z)))
    A[2].append(sum((x, -y, z)))
    A[3].append(sum((x, -y, -z)))
    A[4].append(sum((-x, y, z)))
    A[5].append(sum((-x, y, -z)))
    A[6].append(sum((-x, -y, z)))
    A[7].append(sum((-x, -y, -z)))

cand = []
for i in range(8):
    A[i].sort(reverse=True)
    cand.append(sum(A[i][:M]))

print((max(cand)))
# Original solution
import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
xyz = [[int(x) for x in input().split()] for _ in range(n)]

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

for i in range(n):
    for j in range(1, i + 2):
        if i != 0:
            dp[i][j] = dp[i - 1][j]
            for k in range(i):
                x = dp[k][j - 1][0] + xyz[i][0]
                y = dp[k][j - 1][1] + xyz[i][1]
                z = dp[k][j - 1][2] + xyz[i][2]     
                if abs(x) + abs(y) + abs(z) >= abs(dp[i][j][0]) + abs(dp[i][j][1]) + abs(dp[i][j][2]):
                    dp[i][j] = [x, y, z]
        else:
            dp[0][1] = xyz[i]

a, b, c = dp[-1][m]

print((abs(a) + abs(b) + abs(c)))

# Optimized solution
import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
xyz = [[int(x) for x in input().split()] for _ in range(n)]

ans = 0

for i in range(8):
    i_bin = bin(i)[2:].zfill(3)
    new_xyz_sum = []
    for j in range(n):
        tmp = 0
        x, y, z = xyz[j]
        if i_bin[0] == "0":
            x *= -1
        if i_bin[1] == "0":
            y *= -1
        if i_bin[2] == "0":
            z *= -1
        tmp = x + y + z
        new_xyz_sum.append(tmp)
    new_xyz_sum = sorted(new_xyz_sum, reverse=True)
    ans = max(ans, sum(new_xyz_sum[:m]))

print(ans)
# Original solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from queue import Queue

def solve():
    n, m = list(map(int, input().split()))
    al = [[int(i) for i in input().split()] for _ in range(n)]

    ans = 0
    q = Queue()
    for i in range(n):
        tq = Queue()
        while not q.empty():
            elem = q.get()
            t = [elem[0] + 1, 
                    [
                        elem[1][0] + al[i][0],
                        elem[1][1] + al[i][1],
                        elem[1][2] + al[i][2]
                        ]
                    ]
            if t[0] == m:
                ans = max(ans, abs(t[1][0]) + abs(t[1][1]) + abs(t[1][2]))
            else:
                tq.put(t)
            tq.put(elem)
        q = tq
        q.put([1, [al[i][0], al[i][1], al[i][2]]])
    print(ans)


if __name__=="__main__":
    solve()


# Optimized solution
n, m = list(map(int, input().split()))
l = [[int(i) for i in input().split()] for _ in [0]*n]
ans = 0

def  getmm(k):
  f = lambda x: (x[0] if k & 1 else -x[0]) + (x[1] if k & 2 else -x[1]) + (x[2] if k & 4 else -x[2])
  al = [f(e) for e in l]
  al.sort(reverse=True)
  return sum(al[:m])

for i in range(8):
  ans = max(ans, getmm(i))
print(ans)
# Original solution
N,M=list(map(int,input().split()))

L=[]
for i in range(N):
    x,y,z=list(map(int,input().split()))
    L.append([x,y,z])

A=[[1,1,1],[1,1,-1],[1,-1,1],[1,-1,-1],[-1,1,1],[-1,1,-1],[-1,-1,1],[-1,-1,-1]]

ans=-1000000000000
B=[]
for i in range(8):
    for j in range(N):
        B.append(A[i][0]*L[j][0]+A[i][1]*L[j][1]+A[i][2]*L[j][2])
    B.sort(reverse=True)
    cnt=0
    for k in range(M):
        cnt+=B[k]
    if cnt>ans:
        ans=cnt
    B=[]
print(ans)

# Optimized solution
N,M=list(map(int,input().split()))

LPPP=[]
LPPM=[]
LPMP=[]
LPMM=[]
LMPP=[]
LMPM=[]
LMMP=[]
LMMM=[]
for i in range(N):
    x,y,z=list(map(int,input().split()))
    LPPP.append(x+y+z)
    LPPM.append(x+y-z)
    LPMP.append(x-y+z)
    LPMM.append(x-y-z)
    LMPP.append(-x+y+z)
    LMPM.append(-x+y-z)
    LMMP.append(-x-y+z)
    LMMM.append(-x-y-z)
    
LPPP.sort(reverse=True)
LPPM.sort(reverse=True)
LPMP.sort(reverse=True)
LPMM.sort(reverse=True)
LMPP.sort(reverse=True)
LMPM.sort(reverse=True)
LMMP.sort(reverse=True)
LMMM.sort(reverse=True)
print((max(sum(LPPP[:M]),sum(LPPM[:M]),sum(LPMP[:M]),sum(LPMM[:M]),sum(LMPP[:M]),sum(LMPM[:M]),sum(LMMP[:M]),sum(LMMM[:M]))))
# Original solution
# -*- coding: utf-8 -*-
n,m = list(map(int, input().split()))
xyz = []
for _ in range(n):
    line = list(map(int, input().split()))
    xyz.append(line)

score = -1
for xo in [1,-1]:
    for yo in [1,-1]:
        for zo in [1,-1]:
            idx = sorted(list(range(n)), reverse=True, key=lambda i:xo*xyz[i][0]+yo*xyz[i][1]+zo*xyz[i][2])
            X = 0
            Y = 0
            Z = 0
            for i in range(m):
                X += xyz[idx[i]][0]
                Y += xyz[idx[i]][1]
                Z += xyz[idx[i]][2]
            score = max(score, abs(X)+abs(Y)+abs(Z))

print(score)


# Optimized solution
# -*- coding: utf-8 -*-
n,m = list(map(int, input().split()))
xyz = [list(map(int, input().split())) for _ in range(n)]

res = -1
for xi in [1,-1]:
    for yi in [1,-1]:
        for zi in [1,-1]:
            xyz.sort(reverse=True, key=lambda c:c[0]*xi+c[1]*yi+c[2]*zi)
            t = [0,0,0]
            for i in range(m):
                t[0] += xyz[i][0]
                t[1] += xyz[i][1]
                t[2] += xyz[i][2]

            res = max(res, abs(t[0])+abs(t[1])+abs(t[2]))

print(res)
# Original solution
N,M=list(map(int,input().split()))
cake=[list(map(int,input().split()))for _ in[0]*N]
dp=[[[0]*3]for _ in[0]*(M+1)]
for c in cake:
    for i in range(M-1,-1,-1):
        for t in dp[i]:
            dp[i+1]+=[[c[i]+t[i]for i in range(3)]]
        if len(dp[i])>10:
            a=[sum(t)for t in dp[i]]
            Max,Min=max(a),min(a)
            for s,t,u in dp[i]:
                if s>0 and t>0 and u>0 and s+t+u<Max:dp[i].remove([s,t,u])
                if s<0 and t<0 and u<0 and s+t+u>Min:dp[i].remove([s,t,u])
print((max(sum(map(abs,x))for x in dp[M])))

# Optimized solution
N,M=list(map(int,input().split()))
sums=[[]for _ in[0]*8]
for _ in[0]*N:
    c=list(map(int,input().split()))
    for t in range(8):
        sums[t]+=[sum(c[i]*[-1,1][t&(1<<i)>0]for i in range(3))]
if M:print((max(sum(sorted(sums[i])[-M:])for i in range(8))))
else:print((0))
# Original solution
import copy
n,m = list(map(int,input().split()))

scores = list()
for i in range(n):
    score = list(map(int,input().split()))
    scores.append(score)

smax=None
for i in range(n):
    scores_ = copy.deepcopy(scores)
    for j in range(len(scores[i])):    
        if scores[i][j]<0:
            for k in range(n):
                scores_[k][j] = -scores[k][j]
        else:
            for k in range(n):
                scores_[k][j] = scores[k][j]
    ssum=list()
    for j in range(n):
        ssum.append(sum(scores_[j]))
    ssum.sort()
    tmp=0
    for j in range(m):
        tmp+=ssum[-1]
        ssum.pop()
    if smax==None or tmp>smax:
        smax=tmp

print(smax)

# Optimized solution
import copy
n,m = list(map(int,input().split()))

#取得
scores = list()
for i in range(n):
    score = list(map(int,input().split()))
    scores.append(score)

smax=None
for x in range(2):
    scores_=copy.deepcopy(scores)
    
    for i in range(n):
        scores_[i][0] = pow(-1,x)*scores[i][0]
    for y in range(2):
        for i in range(n):
            scores_[i][1] = pow(-1,y)*scores[i][1]
        for z in range(2):
            for i in range(n):
                scores_[i][2] = pow(-1,z)*scores[i][2]
        
            sumlist=list()
            for i in range(n):
                sumlist.append(sum(scores_[i]))
            sumlist.sort()
            
            tmp=0
            for eat in range(m):
                tmp+=sumlist[-1]
                sumlist.pop()
            if smax==None or tmp>smax:
                smax=tmp
print(smax)
# Original solution
N,M=list(map(int,input().split()))
cakes=[]
for i in range(N):
  x,y,z=list(map(int,input().split()))
  cakes.append([x,y,z])
if M==0:
  print((0))
  quit()
score=[0]*8
score[0]=sum(sorted([c[0]+c[1]+c[2] for c in cakes])[-M:])
score[1]=sum(sorted([c[0]+c[1]-c[2] for c in cakes])[-M:])
score[2]=sum(sorted([c[0]-c[1]+c[2] for c in cakes])[-M:])
score[3]=sum(sorted([c[0]-c[1]-c[2] for c in cakes])[-M:])
score[4]=sum(sorted([-c[0]+c[1]+c[2] for c in cakes])[-M:])
score[5]=sum(sorted([-c[0]+c[1]-c[2] for c in cakes])[-M:])
score[6]=sum(sorted([-c[0]-c[1]+c[2] for c in cakes])[-M:])
score[7]=sum(sorted([-c[0]-c[1]-c[2] for c in cakes])[-M:])
print((max(score)))


# Optimized solution
N,M=list(map(int,input().split()))
cakes=[]
for i in range(N):
  x,y,z=list(map(int,input().split()))
  cakes.append([x,y,z])
if M==0:
  print((0))
  quit()
score=[0]*8
s=sorted([c[0]+c[1]+c[2] for c in cakes])
score[0]=sum(s[-M:])
score[1]=-sum(s[:M])
s=sorted([c[0]+c[1]-c[2] for c in cakes])
score[2]=sum(s[-M:])
score[3]=-sum(s[:M])
s=sorted([c[0]-c[1]+c[2] for c in cakes])
score[4]=sum(s[-M:])
score[5]=-sum(s[:M])
s=sorted([c[0]-c[1]-c[2] for c in cakes])
score[6]=sum(s[-M:])
score[7]=-sum(s[:M])
print((max(score)))
quit()
# Original solution
import itertools
n,m = list(map(int,input().split()))
lst = [list(map(int,input().split())) for _ in range(n)]
res = 0
for l in itertools.permutations(lst, m):
    X,Y,Z = 0,0,0
    for i in range(m):
        x,y,z = l[i][0], l[i][1], l[i][2]
        X += x
        Y += y
        Z += z
    res = max(res, abs(X)+abs(Y)+abs(Z))
print(res)

# Optimized solution
n,m = list(map(int,input().split()))
lst0, lst1, lst2, lst3, lst4, lst5, lst6, lst7 =[],[],[],[],[],[],[],[]
for i in range(n):
    x,y,z = list(map(int,input().split()))
    lst0.append(x+y+z)
    lst1.append(x+y-z)
    lst2.append(x-y+z)
    lst3.append(x-y-z)
    lst4.append(-x+y+z)
    lst5.append(-x+y-z)
    lst6.append(-x-y+z)
    lst7.append(-x-y-z)
lst0.sort(reverse=True)
lst1.sort(reverse=True)
lst2.sort(reverse=True)
lst3.sort(reverse=True)
lst4.sort(reverse=True)
lst5.sort(reverse=True)
lst6.sort(reverse=True)
lst7.sort(reverse=True)

res = []
res.append(sum(lst0[:m]))
res.append(sum(lst1[:m]))
res.append(sum(lst2[:m]))
res.append(sum(lst3[:m]))
res.append(sum(lst4[:m]))
res.append(sum(lst5[:m]))
res.append(sum(lst6[:m]))
res.append(sum(lst7[:m]))
print((max(res)))
# Original solution
n,m = list(map(int,input().split()))
lst0, lst1, lst2, lst3, lst4, lst5, lst6, lst7 =[],[],[],[],[],[],[],[]
for i in range(n):
    x,y,z = list(map(int,input().split()))
    lst0.append(x+y+z)
    lst1.append(x+y-z)
    lst2.append(x-y+z)
    lst3.append(x-y-z)
    lst4.append(-x+y+z)
    lst5.append(-x+y-z)
    lst6.append(-x-y+z)
    lst7.append(-x-y-z)
lst0.sort(reverse=True)
lst1.sort(reverse=True)
lst2.sort(reverse=True)
lst3.sort(reverse=True)
lst4.sort(reverse=True)
lst5.sort(reverse=True)
lst6.sort(reverse=True)
lst7.sort(reverse=True)

res = []
res.append(sum(lst0[:m]))
res.append(sum(lst1[:m]))
res.append(sum(lst2[:m]))
res.append(sum(lst3[:m]))
res.append(sum(lst4[:m]))
res.append(sum(lst5[:m]))
res.append(sum(lst6[:m]))
res.append(sum(lst7[:m]))
print((max(res)))

# Optimized solution
n,m = list(map(int,input().split()))
lst = [[] for _ in range(8)]
for i in range(n):
    x,y,z = list(map(int,input().split()))
    lst[0].append(x+y+z)
    lst[1].append(x+y-z)
    lst[2].append(x-y+z)
    lst[3].append(x-y-z)
    lst[4].append(-x+y+z)
    lst[5].append(-x+y-z)
    lst[6].append(-x-y+z)
    lst[7].append(-x-y-z)
for i in range(8):
    lst[i].sort(reverse=True)
res = []
for i in range(8):
    res.append(sum(lst[i][:m]))
print((max(res)))
# Original solution
N, M = list(map(int, input().split()))
XYZ = [list(map(int, input().split())) for i in range(N)]
X = [XYZ[i][0] for i in range(N)]
Y = [XYZ[i][1] for i in range(N)]
Z = [XYZ[i][2] for i in range(N)]
ans = 0

for i in range(2**M - 1, 2**N - 2**(N - M) + 1):
    b = bin(i)[2:]
    if len(b) != N:
        f = [0 for i in range(N-len(b))] + [int(a) for a in b]
    else:
        f = [int(a) for a in b]
    if sum(f) == M:
        ans_x = abs(sum([x * y for x, y in zip(X, f)]))
        ans_y = abs(sum([x * y for x, y in zip(Y, f)]))
        ans_z = abs(sum([x * y for x, y in zip(Z, f)]))
        ans = max(ans, (ans_x + ans_y + ans_z))

print(ans)

# Optimized solution
N, M = list(map(int, input().split()))
cakes = []
for i in range(N):
    x, y, z = list(map(int, input().split()))
    cakes.append([x, y, z])


if M == 0:
    print((0))
    quit()
score = [0]*8
s = sorted([c[0]+c[1]+c[2] for c in cakes])
score[0] = sum(s[-M:])
score[1] = -sum(s[:M])
s = sorted([c[0]+c[1]-c[2] for c in cakes])
score[2] = sum(s[-M:])
score[3] = -sum(s[:M])
s = sorted([c[0]-c[1]+c[2] for c in cakes])
score[4] = sum(s[-M:])
score[5] = -sum(s[:M])
s = sorted([c[0]-c[1]-c[2] for c in cakes])
score[6] = sum(s[-M:])
score[7] = -sum(s[:M])
print((max(score)))
# Original solution
import itertools


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

scores = [list(map(int,input().split())) for _ in range(n) ]

max_socre = 0
for cakes in itertools.combinations(scores, m):
    b = 0
    t = 0
    p = 0
    for cake in cakes:
        b += cake[0]
        t += cake[1]
        p += cake[2]

    score = abs(b) + abs(t) + abs(p)
    if score > max_socre:
        max_socre = score

print(max_socre)



# Optimized solution
import itertools


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

scores = [list(map(int,input().split())) for _ in range(n) ]

# 8 pattern

max_of_sum = 0
for pick in range(8):
    sum_scores = []
    for score in scores:
        sum_of_score = 0
        if pick & 0b001 == 0:
            # plus
            sum_of_score += score[0]
        else:
            sum_of_score -= score[0]

        if pick & 0b010 == 0:
            # plus
            sum_of_score += score[1]
        else:
            sum_of_score -= score[1]

        if pick & 0b100 == 0:
            # plus
            sum_of_score += score[2]
        else:
            sum_of_score -= score[2]

        sum_scores.append(sum_of_score)

    sum_scores.sort(reverse=True)
    current_sum = sum(sum_scores[:m])
    if current_sum > max_of_sum:
        max_of_sum = current_sum

print(max_of_sum)
# Original solution
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = list(map(int, input().split()))
X, Y, Z = [0] * N, [0] * N, [0] * N

for i in range(N):
    X[i], Y[i], Z[i] = list(map(int, input().split()))

codes = [[1, 1, 1], [1, 1, -1], [1, -1, 1], [1, -1, -1], [-1, 1, 1], [-1, 1, -1], [-1, -1, 1], [-1, -1, -1]]


def calc(code, idx):
    return code[0] * X[idx] + code[1] * Y[idx] + code[2] * Z[idx]


ans = 0
INF = 1 << 60
for code in codes:
    dp = [-INF] * (M + 1)
    dp[0] = 0
    for i in range(N):
        tmp = [-INF] * (M + 1)
        tmp[0] = 0
        for j in range(M, 0, -1):
            if dp[j - 1] >= 0:
                tmp[j] = max(dp[j], dp[j - 1] + calc(code, i))

        dp = tmp
    #     print("", dp)
    # print(dp)
    ans = max(ans, dp[M])

print(ans)

# Optimized solution
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = list(map(int, input().split()))
X, Y, Z = [0] * N, [0] * N, [0] * N

for i in range(N):
    X[i], Y[i], Z[i] = list(map(int, input().split()))

codes = [[1, 1, 1], [1, 1, -1], [1, -1, 1], [1, -1, -1], [-1, 1, 1], [-1, 1, -1], [-1, -1, 1], [-1, -1, -1]]


def calc(code, idx):
    return code[0] * X[idx] + code[1] * Y[idx] + code[2] * Z[idx]


INF = 1 << 60
ans = -INF
for code in codes:
    ar = [0] * N

    for i in range(N):
        ar[i] = calc(code, i)

    ar.sort(reverse=True)

    ans = max(ans, sum(ar[:M]))

print(ans)
# Original solution
n,m = list(map(int,input().split()))
xyz = [list(map(int,input().split())) for i in range(n)]

dp = [[[[0,0,0] for k in range(8)] for j in range(n+1)] for i in range(n+1)]

for i in range(n):
    for j in range(1,i+2):
        for k in range(8):
            l,r = 0,0
            for d in range(3):
                if k>>d&1:
                    l += dp[i][j-1][k][d] + xyz[i][d]
                    r += dp[i][j][k][d]
                else:
                    l -= dp[i][j-1][k][d] + xyz[i][d]
                    r -= dp[i][j][k][d]
            if l > r:
                for d in range(3):
                    dp[i+1][j][k][d] = dp[i][j-1][k][d] + xyz[i][d]
            else:
                dp[i+1][j][k] = dp[i][j][k]

ans = 0
for k in range(8):
    a = 0
    for d in range(3):
        if k>>d&1:
            a += dp[n][m][k][d]
        else:
            a -= dp[n][m][k][d]
    ans = max(ans,a)
print(ans)



# Optimized solution
n,m = list(map(int,input().split()))
xyz = [list(map(int,input().split())) for i in range(n)]
ans = 0
for i in range(8):
    s = []
    for j in range(n):
        a = 0
        for k in range(3):
            if i>>k&1:
                a += xyz[j][k]
            else:
                a -= xyz[j][k]
        s.append(a)
    s.sort()
    ans = max(ans,sum(s[n-m:]))
print(ans)
# Original solution
N,M = list(map(int,input().split()))
XYZ = [tuple(map(int,input().split())) for _ in range(N)]
ans = 0
for b in range(8):
	dp = [0]
	for x,y,z in XYZ:
		if b&1: x *= -1
		if b&2: y *= -1
		if b&4: z *= -1
		v = x+y+z
		dp2 = dp[:]
		for i in range(len(dp)-1,-1,-1):
			if i < M:
				if i+1 >= len(dp2):
					dp2.append(dp[i] + v)
				else:
					dp2[i+1] = max(dp2[i+1], dp[i] + v)
		dp = dp2
	ans = max(ans, dp[-1])
print(ans)

# Optimized solution
N,M = list(map(int,input().split()))
XYZ = [tuple(map(int,input().split())) for _ in range(N)]
ans = 0
for b in range(8):
	arr = []
	for x,y,z in XYZ:
		if b&1: x *= -1
		if b&2: y *= -1
		if b&4: z *= -1
		arr.append(x+y+z)
	arr.sort(reverse=True)
	ans = max(ans, sum(arr[:M]))
print(ans)
# Original solution
# -*- coding: utf-8 -*-

n, m = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(n)]
ans = 0

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+A[i-1][0]+A[i-1][1]+A[i-1][2])
ans = max(ans, dp[n][m])

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+A[i-1][0]+A[i-1][1]-A[i-1][2])
ans = max(ans, dp[n][m])

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+A[i-1][0]-A[i-1][1]+A[i-1][2])
ans = max(ans, dp[n][m])

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+A[i-1][0]-A[i-1][1]-A[i-1][2])
ans = max(ans, dp[n][m])

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-A[i-1][0]+A[i-1][1]+A[i-1][2])
ans = max(ans, dp[n][m])

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-A[i-1][0]+A[i-1][1]-A[i-1][2])
ans = max(ans, dp[n][m])

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-A[i-1][0]-A[i-1][1]+A[i-1][2])
ans = max(ans, dp[n][m])

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-A[i-1][0]-A[i-1][1]-A[i-1][2])
ans = max(ans, dp[n][m])

print(ans)


# Optimized solution
# -*- coding: utf-8 -*-

n, m = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(n)]
ans = 0

for i in range(8):
    value_list = []
    for a in A:
        value_list.append((2*(i&1)-1)*a[0] + (2*((i>>1)&1)-1)*a[1] + (2*((i>>2)&1)-1)*a[2])
    value_list.sort(reverse=True)
    ans = max(ans, sum(value_list[:m]))

print(ans)
# Original solution
N,M=list(map(int,input().split()))
X = [[] for i in range(8)]
for i in range(N):
    x,y,z=list(map(int,input().split()))
    for i in range(8):
        X[i].append(int(2*((i%2)-1/2))*x + int(2*(((i//2)%2)-1/2))*y + int(2*(((i//4)%2)-1/2))*z)
ans=0
for i in range(8):
    X[i].sort()
    X[i]=X[i][::-1]
    ans=max(sum(X[i][:M]),ans)
    
print(ans)

# Optimized solution
N,M = list(map(int,input().split()))

X = []

for i in range(N):
    x,y,z = list(map(int,input().split()))
    X.append([x,y,z])

max_score = 0
for i in range(8):
    a = i%2
    j = i//2
    b = j%2
    k = j//2
    c = k%2
    a,b,c = 2*a-1,2*b-1,2*c-1
    Z = []
    for j in range(N):
        Z.append(a*X[j][0]+b*X[j][1]+c*X[j][2])
    Z.sort(reverse=True)
    max_score = max(sum(Z[:M]),max_score)

print(max_score)
# Original solution
from itertools import product
n, m = list(map(int, input().split()))
xyz = [tuple(map(int, input().split())) for _ in range(n)]


ans = 0
for subset in product((-1, 1), repeat=3):
    INF = 10**18
    dp = [-INF]*(n+1)
    dp[0] = 0

    def func(xyz):
        return sum(x*a for x, a in zip(xyz, subset))

    values = list(map(func, xyz))
    for i, val in enumerate(values, 1):
        for j in reversed(list(range(1, i+1))):
            dp[j] = max(dp[j-1]+val, dp[j])
    if ans < dp[m]:
        ans = dp[m]

print(ans)

# Optimized solution
from itertools import product
n, m = list(map(int, input().split()))
xyz = [tuple(map(int, input().split()))for _ in range(n)]

ans = 0
for subset in product((-1, 1), repeat=3):
    def func(xyz):
        return sum(x*a for x, a in zip(xyz, subset))
    score = sum(sorted(map(func, xyz), reverse=True)[:m])
    if ans < score:
        ans = score
print(ans)
# Original solution
n, m = list(map(int, input().split()))
v = [list(map(int, input().split())) for i in range(n)]
ans = 0
op = [-1,1]
for i in range(2):
    for j in range(2):
        for k in range(2):
            sx, sy, sz = op[i], op[j], op[k]
            dp = [0]*(m+1)
            for l, (x, y, z) in enumerate(v):
                x *= sx
                y *= sy
                z *= sz
                score = x+y+z
                for h in range(min(m,l+1),0,-1):
                    if l < m and h == min(m,l+1):
                        dp[h] = dp[h-1]+score
                    else:
                        dp[h] = max(dp[h], dp[h-1]+score)
            ans = max(ans, dp[-1])
print(ans)

# Optimized solution
n, m = list(map(int, input().split()))
v = [list(map(int, input().split())) for i in range(n)]
ans = 0
op = [-1,1]
for i in range(2):
    for j in range(2):
        for k in range(2):
            sx, sy, sz = op[i], op[j], op[k]
            dp = [-float("inf")]*(m+1)
            dp[0] = 0
            for l, (x, y, z) in enumerate(v):
                x *= sx
                y *= sy
                z *= sz
                score = x+y+z
                for h in range(min(m,l+1),0,-1):
                    dp[h] = max(dp[h], dp[h-1]+score)
            ans = max(ans, dp[-1])
print(ans)