Farmer John debe tomar su examen anual de licencia agrícola, con $N$ preguntas verdadero/falso ($1 \le N \le 1,000,000$). Tras su mal resultado del año pasado, Bessie quiere ayudar.
Bessie sabe por información interna que la cantidad de respuestas verdaderas es una de $t_{1}$, $t_{2}$, $t_{3}$, ..., $t_{K}$ ($0 \le t_i \le N; 0 \le K \le 10,000$), pero no sabe respuesta de ninguna pregunta concreta. Busca la mejor puntuación garantizada a FJ al usar cuidadosamente esta información, aun sin conocer respuestas reales.
Considere $N=6$ preguntas con0 o3 respuestas verdaderas. FJ garantiza al menos3 correctas: contestando falso en todas, si hay0 verdaderas acierta6; si hay3 acierta3. Así marcar todo falso garantiza3 aun sin conocer respuestas.
Una estrategia peor es adivinar3 verdaderas y3 falsas. Si ninguna es verdadera, acierta las3 marcadas falsas. Si3 son verdaderas puede acertar0: las3 marcadas verdaderas son falsas y las otras3 son verdaderas. Aunque marcar todo falso daría3, escoger3 verdaderas no garantiza ni1 acierto, por lo que no garantiza ninguno. FJ debe usar la estrategia del párrafo anterior.
Dada la información de Bessie, determina los aciertos siempre garantizados usando óptimamente dicha información.
Entrada
- Línea1: dos enteros separados por espacio $N$ y $K$.
- Líneas $2..K+1$: línea $i+1$ contiene un entero $t_{i}$.
Salida
- Línea1: un entero, la mejor puntuación garantizada a FJ.
Ejemplos
Entrada 1
6 2 0 3
Salida 1
3
Autor del problema: Tom Conerly, 2010