Mex Boxes

AtCoder

IDkeyence2021_b

Time2000ms

Memory256MB

Difficulty—

Snuke has $N$ balls, each with an integer written on it. The numbers on the balls are $a_1, a_2, \ldots, a_N$. He has decided to put these $N$ balls in $K$ boxes. Every ball must be in some box, but there may be boxes with zero or multiple balls. After he put the balls in the boxes, the lid of each box will show an integer. Let $x$ be the integer shown on a box. $x$ is the minimum **non-negative** integer such that the box contains no ball with $x$. For example, the lid of an empty box will show $0$; the lid of a box with balls $0, 1, 3, 5$ will show $2$; the lid of a box with balls $1, 2, 3$ will show $0$. Find the maximum possible sum of the integers the lids show. ## Constraints * All values in input are integers. * $1 \leq K \leq N \leq 3 \times 10^{5}$ * $0 \leq a_i < N$ ## Input Input is given from Standard Input in the following format: $N$ $K$ $a_1$ $a_2$ $\cdots$ $a_N$ [samples]

Samples

Input #1

4 2
0 1 0 2

Output #1

4

*   An optimal solution is to allocate the sets of balls ${0,1,2 },{0}$ to the boxes.
*   In this case, the lids show $3, 1$, respectively, for a total of $4$.

Input #2

5 2
0 1 1 2 3

Output #2

4

*   An optimal solution is to allocate the (multi)sets of balls ${0,1,1,2,3}, {}$ to the boxes.
*   In this case, the lids show $4, 0$, respectively, for a total of $4$.
*   Note that we may have empty boxes.

Input #3

20 4
6 2 6 8 4 5 5 8 4 1 7 8 0 3 6 1 1 8 3 0

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Mex Boxes",
    "description": {
      "content": "Snuke has $N$ balls, each with an integer written on it. The numbers on the balls are $a_1, a_2, \\ldots, a_N$. He has decided to put these $N$ balls in $K$ boxes. Every ball must be in some box, but t",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "keyence2021_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Snuke has $N$ balls, each with an integer written on it. The numbers on the balls are $a_1, a_2, \\ldots, a_N$.\nHe has decided to put these $N$ balls in $K$ boxes. Every ball must be in some box, but t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments