output_description: Print the maximum possible value of (the absolute value of the total beauty) +
  (the absolute value of the total tastiness) + (the absolute value of the total
  popularity) for the set of cakes that Ringo chooses.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      x_1 y_1 z_1
      x_2 y_2 z_2
       :  :
      x_N y_N z_N
attempt: import sys
  
  
  def input():
      return sys.stdin.readline().strip()
  
  
  def quickSelect(A, k):
      """
      長さnの配列Aの中からk番目(1-indexed)に小さい値を線形時間で求めるアルゴリズム。
      動作原理は次を参照：http://www.flint.jp/blog/?entry=109
      処理の流れは次を参照：https://naoyat.hatenablog.jp/entry/median-of-medians
  
      使用例：quickSelect([2,7,1,8,2], 5, 3) => 2
      """
      n = len(A)
      while True:
          B = A
          m = n
  
          # 1.配列からmedian of mediansにより適切なpivotを選択（25%~75%に収まる）
          while m > 5:
              medians = []
              rem = 0
              for i in range(m // 5):
                  sortB = sorted(B[i * 5 : (i + 1) * 5])
                  medians.append(sortB[2])
              if m % 5 != 0:
                  sortB = sorted(B[(m // 5) * 5 :])
                  medians.append(sortB[(m - (m // 5) * 5) // 2])
                  rem = 1
              B = medians
              m = m // 5 + rem
          B.sort()
          pivot = B[m // 2]
  
          # 2.pivotを軸に大小で左右に分ける
          left = []
          right = []
          left_num = 0
          right_num = 0
          for a in A:
              if a < pivot:
                  left.append(a)
                  left_num += 1
              elif a > pivot:
                  right.append(a)
                  right_num += 1
          if left_num < k <= n - right_num:
              return pivot
          elif left_num < k:
              A = right
              k -= n - right_num
              n = right_num
          else:
              A = left
              n = left_num
  
  
  def main():
      N, M = map(int, input().split())
      cakes = [(0, 0, 0)]
      for _ in range(N):
          x, y, z = map(int, input().split())
          cakes.append((x, y, z))
  
      """
      quickSelectによりO(N)で解ける別解を実装。
      x+y+zやx-y-z等のそれぞれに対してcakesをソートして大きい値から取れば良い。
      """
  
      ans = 0
      for i in range(8):
          sorted_cakes = []
          for j in range(1, N + 1):
              S = 0
              for k in range(3):  # iの立っているビットでx, y, zの符号を管理している！！
                  if i & (1 << k):
                      S += cakes[j][k]
                  else:
                      S -= cakes[j][k]
              sorted_cakes.append(S)
  
          # ここでsorted_cakesのM番目に大きな値（＝(N - M + 1)番目に小さな値）をquickSelectで求める
          # あとはその数以上なら評価に加算すれば良い
          val = 0
          bound = quickSelect(sorted_cakes, N - M + 1)
          cnt = 0
          for c in sorted_cakes:
              if c > bound:
                  val += c
                  cnt += 1
          val += bound * (M - cnt)
          ans = max(ans, val)
      print(ans)
  
  
  if __name__ == "__main__":
      main()
  
problem_description: Statement
  
  Takahashi became a pastry chef and opened a shop _La Confiserie d'ABC_ to
  celebrate AtCoder Beginner Contest 100.
  
  The shop sells N kinds of cakes.  
  Each kind of cake has three parameters "beauty", "tastiness" and "popularity".
  The i-th kind of cake has the beauty of x_i, the tastiness of y_i and the
  popularity of z_i.  
  These values may be zero or negative.
  
  Ringo has decided to have M pieces of cakes here. He will choose the set of
  cakes as follows:
  
    * Do not have two or more pieces of the same kind of cake.
    * Under the condition above, choose the set of cakes to maximize (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity).
  
  Find the maximum possible value of (the absolute value of the total beauty) +
  (the absolute value of the total tastiness) + (the absolute value of the total
  popularity) for the set of cakes that Ringo chooses.
samples: [{"input": "5 3\n    3 1 4\n    1 5 9\n    2 6 5\n    3 5 8\n    9 7 9", "output": "56\n    \n\nConsider having the 2-nd, 4-th and 5-th kinds of cakes. The total beauty,\ntastiness and popularity will be as follows:\n\n  * Beauty: 1 + 3 + 9 = 13\n  * Tastiness: 5 + 5 + 7 = 17\n  * Popularity: 9 + 8 + 9 = 26\n\nThe value (the absolute value of the total beauty) + (the absolute value of\nthe total tastiness) + (the absolute value of the total popularity) here is 13\n+ 17 + 26 = 56. This is the maximum value.\n\n* * *"}, {"input": "5 3\n    1 -2 3\n    -4 5 -6\n    7 -8 -9\n    -10 11 -12\n    13 -14 15", "output": "54\n    \n\nConsider having the 1-st, 3-rd and 5-th kinds of cakes. The total beauty,\ntastiness and popularity will be as follows:\n\n  * Beauty: 1 + 7 + 13 = 21\n  * Tastiness: (-2) + (-8) + (-14) = -24\n  * Popularity: 3 + (-9) + 15 = 9\n\nThe value (the absolute value of the total beauty) + (the absolute value of\nthe total tastiness) + (the absolute value of the total popularity) here is 21\n+ 24 + 9 = 54. This is the maximum value.\n\n* * *"}, {"input": "10 5\n    10 -80 21\n    23 8 38\n    -94 28 11\n    -26 -2 18\n    -69 72 79\n    -26 -86 -54\n    -72 -50 59\n    21 65 -32\n    40 -94 87\n    -62 18 82", "output": "638\n    \n\nIf we have the 3-rd, 4-th, 5-th, 7-th and 10-th kinds of cakes, the total\nbeauty, tastiness and popularity will be -323, 66 and 249, respectively.  \nThe value (the absolute value of the total beauty) + (the absolute value of\nthe total tastiness) + (the absolute value of the total popularity) here is\n323 + 66 + 249 = 638. This is the maximum value.\n\n* * *"}, {"input": "3 2\n    2000000000 -9000000000 4000000000\n    7000000000 -5000000000 3000000000\n    6000000000 -1000000000 8000000000", "output": "30000000000\n    \n\nThe values of the beauty, tastiness and popularity of the cakes and the value\nto be printed may not fit into 32-bit integers."}]