Farmer John deve fazer a prova anual da licença agrícola, com $N$ questões verdadeiro/falso ($1 \le N \le 1,000,000$). Após seu resultado ruim no ano passado, Bessie quer ajudar.
Bessie sabe por informação interna que a quantidade de respostas verdadeiras é uma de $t_{1}$, $t_{2}$, $t_{3}$, ..., $t_{K}$ ($0 \le t_i \le N; 0 \le K \le 10,000$), mas não conhece resposta de nenhuma questão específica. Quer a melhor pontuação garantida a FJ usando cuidadosamente essa informação, mesmo sem conhecer respostas reais.
Considere $N=6$ questões com0 ou3 respostas verdadeiras. FJ garante pelo menos3 acertos: marcando tudo falso, se há0 verdadeiras acerta6; se há3 acerta3. Assim tudo falso garante3 sem conhecer respostas.
Uma estratégia pior é adivinhar3 verdadeiras e3 falsas. Se nenhuma é verdadeira, acerta as3 marcadas falsas. Se3 são verdadeiras pode acertar0: as3 marcadas verdadeiras são falsas e as outras3 são verdadeiras. Embora tudo falso daria3, escolher3 verdadeiras não garante nem1 acerto; não garante nenhum. FJ deve usar a estratégia do parágrafo anterior.
Dada a informação de Bessie, determine os acertos sempre garantidos usando-a otimamente.
Entrada
- Linha1: dois inteiros separados por espaço $N$ e $K$.
- Linhas $2..K+1$: linha $i+1$ contém um inteiro $t_{i}$.
Saída
- Linha1: um inteiro, a melhor pontuação garantida a FJ.
Exemplos
Entrada 1
6 2 0 3
Saída 1
3
Autor do problema: Tom Conerly, 2010