{"raw_statement":[{"iden":"problem statement","content":"Takahashi became a pastry chef and opened a shop _La Confiserie d'ABC_ to celebrate AtCoder Beginner Contest 100.\nThe shop sells $N$ kinds of cakes.  \nEach 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$.  \nThese values may be zero or negative.\nRingo has decided to have $M$ pieces of cakes here. He will choose the set of cakes as follows:\n\n*   Do not have two or more pieces of the same kind of cake.\n*   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).\n\nFind 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."},{"iden":"constraints","content":"*   $N$ is an integer between $1$ and $1 \\ 000$ (inclusive).\n*   $M$ is an integer between $0$ and $N$ (inclusive).\n*   $x_i, y_i, z_i \\ (1 \\leq i \\leq N)$ are integers between $-10 \\ 000 \\ 000 \\ 000$ and $10 \\ 000 \\ 000 \\ 000$ (inclusive)."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$x_1$ $y_1$ $z_1$\n$x_2$ $y_2$ $z_2$\n $:$  $:$\n$x_N$ $y_N$ $z_N$"},{"iden":"sample input 1","content":"5 3\n3 1 4\n1 5 9\n2 6 5\n3 5 8\n9 7 9"},{"iden":"sample output 1","content":"56\n\nConsider having the $2$\\-nd, $4$\\-th and $5$\\-th kinds of cakes. The total beauty, tastiness 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 the total tastiness) + (the absolute value of the total popularity) here is $13 + 17 + 26 = 56$. This is the maximum value."},{"iden":"sample input 2","content":"5 3\n1 -2 3\n-4 5 -6\n7 -8 -9\n-10 11 -12\n13 -14 15"},{"iden":"sample output 2","content":"54\n\nConsider having the $1$\\-st, $3$\\-rd and $5$\\-th kinds of cakes. The total beauty, tastiness 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 the total tastiness) + (the absolute value of the total popularity) here is $21 + 24 + 9 = 54$. This is the maximum value."},{"iden":"sample input 3","content":"10 5\n10 -80 21\n23 8 38\n-94 28 11\n-26 -2 18\n-69 72 79\n-26 -86 -54\n-72 -50 59\n21 65 -32\n40 -94 87\n-62 18 82"},{"iden":"sample output 3","content":"638\n\nIf we have the $3$\\-rd, $4$\\-th, $5$\\-th, $7$\\-th and $10$\\-th kinds of cakes, the total beauty, tastiness and popularity will be $-323$, $66$ and $249$, respectively.  \nThe value (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) here is $323 + 66 + 249 = 638$. This is the maximum value."},{"iden":"sample input 4","content":"3 2\n2000000000 -9000000000 4000000000\n7000000000 -5000000000 3000000000\n6000000000 -1000000000 8000000000"},{"iden":"sample output 4","content":"30000000000\n\nThe values of the beauty, tastiness and popularity of the cakes and the value to be printed may not fit into 32-bit integers."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}