Patisserie ABC

AtCoder

IDabc100_d

Time2000ms

Memory256MB

Difficulty—

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. ## Constraints * $N$ is an integer between $1$ and $1 \ 000$ (inclusive). * $M$ is an integer between $0$ and $N$ (inclusive). * $x_i, y_i, z_i \ (1 \leq i \leq N)$ are integers between $-10 \ 000 \ 000 \ 000$ and $10 \ 000 \ 000 \ 000$ (inclusive). ## Input 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$ [samples]

Samples

Input #1

Output #1

56

Consider having the $2$\-nd, $4$\-th and $5$\-th kinds of cakes. The total beauty, tastiness and popularity will be as follows:

*   Beauty: $1 + 3 + 9 = 13$
*   Tastiness: $5 + 5 + 7 = 17$
*   Popularity: $9 + 8 + 9 = 26$

The 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.

Input #2

Output #2

54

Consider having the $1$\-st, $3$\-rd and $5$\-th kinds of cakes. The total beauty, tastiness and popularity will be as follows:

*   Beauty: $1 + 7 + 13 = 21$
*   Tastiness: $(-2) + (-8) + (-14) = -24$
*   Popularity: $3 + (-9) + 15 = 9$

The 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.

Input #3

10 5
10 -80 21
23 8 38
-94 28 11
-26 -2 18
-69 72 79
-26 -86 -54
-72 -50 59
21 65 -32
40 -94 87
-62 18 82

Output #3

638

If 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.  
The 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.

Input #4

3 2
2000000000 -9000000000 4000000000
7000000000 -5000000000 3000000000
6000000000 -1000000000 8000000000

Output #4

30000000000

The values of the beauty, tastiness and popularity of the cakes and the value to be printed may not fit into 32-bit integers.

API Response (JSON)

{
  "problem": {
    "name": "Patisserie ABC",
    "description": {
      "content": "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\", ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc100_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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\", ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments