import Data.Array
import Data.Array.ST
import Control.Monad
import Control.Monad.ST

type Norm=(Integer,Integer,Integer)->Integer

evaler::(Bool,Bool,Bool)->Norm
evaler (a,b,c) (x,y,z) = 0+(if a then x else (-x))+(if b then y else (-y))+(if c then z else (-z))



gen_dp::Norm->Int->Array Int (Integer,Integer,Integer)->Array (Int,Int) Integer
gen_dp norm m ar = let (i,f) = bounds ar in
                    runSTArray $ do
                        table<-newArray_ ((0,i),(m,f))
                        forM_ [i..f] (\j -> writeArray table (0,j) 0)
                        writeArray table (1,i) (norm (ar!(1)))
                        forM_ [(1+k,i+k)|k<-[1..(m-1)]] (\(n,j)->do
                                                                v<-readArray table (n-1,j-1)
                                                                writeArray table (n,j) (v+(norm (ar!j))))
                        forM_ (concat [[(n,j)|j<-[(i+n)..f]]|n<-[1..m]]) (\(n,j)->do
                                                                                not_j<-readArray table (n,j-1)
                                                                                v<-readArray table (n-1,j-1)
                                                                                let eat_j = v+(norm (ar!j))
                                                                                writeArray table (n,j) (max not_j eat_j) )
                        return table

one_solver::Norm->Int->Array Int (Integer,Integer,Integer)->Integer
one_solver norm m ar = let dp = gen_dp norm m ar in
                       let (_,f) = bounds dp in
                       dp!f

solver::Int->Array Int (Integer,Integer,Integer)->Integer
solver m ar = maximum [one_solver (evaler bbb) m ar | bbb<-all_3bit]

all_3bit::[(Bool,Bool,Bool)]
all_3bit = concat [concat [[(b1,b2,b3)|b1<-[True,False]]|b2<-[True,False]]|b3<-[True,False]]


main::IO()
main=do
  nmc<-getLine
  let n:m:[]=map read (words nmc)::[Int]
  ss<-forM [1..n] (\_-> getLine)
  let ls = map (\s-> let x:y:z:[] = map read (words s) in (x,y,z)) ss ::[(Integer,Integer,Integer)]
  let ar = listArray (1,n) ls
  print (solver m ar)
