Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ENVEL09 - Número de Envelopes

 

Aldo é um garoto muito esperto que adora promoções e sorteios. Como já participou de muitas promoções da forma “para participar, envie n rótulos de produtos ...”, Aldo tem o costume de guardar o rótulo de todos os produtos que compra. Dessa forma, sempre que uma empresa faz uma promoção ele já tem um monte de rótulos para mandar.

A SBC (Super Balas e Caramelos) está fazendo uma nova promoção, e, como era de se esperar, Aldo quer participar. Para participar da promoção é preciso enviar um envelope contendo um rótulo de cada tipo de bala que a SBC produz. Por exemplo, se a SBC produz 3 tipos de balas, A, B, C, e uma pessoa tem 3 rótulos de A, 3 de B e 2 de C, ela pode enviar no máximo 2 envelopes, já que falta um rótulo de C para compor o terceiro envelope. Não há limite para o número de envelopes que uma pessoa pode enviar.

Balas são a segunda coisa de que Aldo mais gosta (a primeira como você sabe são promoções). Por causa disso a quantidade de rótulos de balas que ele tem é muito grande, e ele não está conseguindo determinar a quantidade máxima de envelopes que ele pode enviar.

Como você é o melhor amigo de Aldo ele pediu sua ajuda para fazer o cálculo, de modo que ele compre o número exato de envelopes.

Tarefa

Você deve escrever um programa que, a partir da lista de rótulos de Aldo, calcula o número máximo de envelopes válidos que ele pode enviar.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado).

A primeira linha contém dois números inteiros N (1 ≤ N ≤ 1000000) e K (1 ≤ K ≤ 1000) representando respectivamente a quantidade de rótulos de balas que Aldo possui e o número de tipos diferentes de bala que a SBC produz. Os tipos de balas são identificados por inteiros de 1 a K. A segunda linha contém N números inteiros Xi, cada um representando um rótulo de bala que Aldo possui (1 ≤ Xi ≤ K, para 1 ≤ i ≤ N).

Saída

Seu programa deve imprimir, na saída padrão, o número máximo de envelopes válidos que Aldo pode enviar.

Exemplos

Entrada
10 2
1 1 1 1 1 2 2 2 2 2

Saída
5

Entrada
20 5
1 2 3 4 1 2 3 4 1 2 3 4 5 1 2 3 4 5 4 4

Saída
2

Adicionado por:Wanderley Guimarăes
Data:2012-05-31
Tempo limite:0.166s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2009 - fase 1 nível 1

hide comments
2016-04-22 02:54:54 Elsio [UFABC]
Em caso de TLE, lembre-se de que o spoj não gosta do cin
2014-08-11 20:06:29 Pedro


Last edit: 2014-11-17 18:36:01
2013-05-31 00:17:21 Raphael Medeiros


Last edit: 2013-06-01 20:06:31
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.