Streamline

AtCoder

IDabc117_c

Time2000ms

Memory256MB

Difficulty—

We will play a one-player game using a number line and $N$ pieces. First, we place each of these pieces at some integer coordinate. Here, multiple pieces can be placed at the same coordinate. Our objective is to visit all of the $M$ coordinates $X_1, X_2, ..., X_M$ with these pieces, by repeating the following move: **Move**: Choose a piece and let $x$ be its coordinate. Put that piece at coordinate $x+1$ or $x-1$. Note that the coordinates where we initially place the pieces are already regarded as visited. Find the minimum number of moves required to achieve the objective. ## Constraints * All values in input are integers. * $1 \leq N \leq 10^5$ * $1 \leq M \leq 10^5$ * $-10^5 \leq X_i \leq 10^5$ * $X_1, X_2, ..., X_M$ are all different. ## Input Input is given from Standard Input in the following format: $N$ $M$ $X_1$ $X_2$ $...$ $X_M$ [samples]

Samples

Input #1

2 5
10 12 1 2 14

Output #1

5

The objective can be achieved in five moves as follows, and this is the minimum number of moves required.

*   Initially, put the two pieces at coordinates $1$ and $10$.
*   Move the piece at coordinate $1$ to $2$.
*   Move the piece at coordinate $10$ to $11$.
*   Move the piece at coordinate $11$ to $12$.
*   Move the piece at coordinate $12$ to $13$.
*   Move the piece at coordinate $13$ to $14$.

Input #2

3 7
-10 -3 0 9 -100 2 17

Output #2

Input #3

100 1
-100000

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Streamline",
    "description": {
      "content": "We will play a one-player game using a number line and $N$ pieces. First, we place each of these pieces at some integer coordinate. Here, multiple pieces can be placed at the same coordinate. Our obje",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc117_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We will play a one-player game using a number line and $N$ pieces.\nFirst, we place each of these pieces at some integer coordinate.\nHere, multiple pieces can be placed at the same coordinate.\nOur obje...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments