Cajas Mex


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 1G

Author:
Problem type
Allowed languages
C, C++, Python, Rust

Descripción

¡Finalmente Marco ha podido debutar en la Copa de la PlayStation Network (PSN) y ha conseguido llegar a la final! Como desafío Marco tiene N bolas, cada una con un número entero escrito en ella. Los números en las bolas son a_1, a_2, \ldots, a_N.

Ahora tiene que colocar estas N bolas en K cajas. Cada bola debe estar en alguna caja, pero puede haber cajas sin bolas o con múltiples bolas. Después de colocar las bolas en las cajas, la tapa de cada caja mostrará un número entero. Sea x el entero mostrado en una caja, x es el entero no negativo mínimo tal que la caja no contiene ninguna bola con x. Por ejemplo, la tapa de una caja vacía mostrará 0; la tapa de una caja con bolas 0, 1, 3, 5 mostrará 2; la tapa de una caja con bolas 1, 2, 3 mostrará 0.

Encuentra la suma máxima posible de los enteros mostrados en las tapas para que Marco logre ganar la final.

Entrada

La primera línea de la entrada contiene dos enteros N y K (1 \le K \le N \le 3 \times 10^5).

La segunda y última línea de la entrada contiene los valores a_1, a_2, \ldots, a_N (0 \le a_i < N)

Salida

Imprime la suma máxima posible de los enteros mostrados en las tapas.

Ejemplos

Entrada 1
4 2
0 1 0 2
Salida 1
4
  • Una solución óptima es asignar los conjuntos de bolas \{0,1,2\}, \{0\} a las cajas.
  • En este caso, las tapas muestran 3,1, respectivamente, para un total de 4.
Entrada 2
5 2
0 1 1 2 3
Salida 2
4
  • Una solución óptima es asignar los (multi)conjuntos de bolas \{0,1,1,2,3\}, \{\} a las cajas.
  • En este caso, las tapas muestran 4, 0, respectivamente, para un total de 4.
  • Tenga en cuenta que podemos tener cajas vacías.
Entrada 3
20 4
6 2 6 8 4 5 5 8 4 1 7 8 0 3 6 1 1 8 3 0
Salida 3
11

Comments


  • -2
    Jose_Ernesto  commented on Dec. 19, 2023, 8:03 p.m.

    Que alguien revise mi código


  • -2
    Jose_Ernesto  commented on Dec. 19, 2023, 8:03 p.m.

    Ayudaa!!!