Farmer John deve sostenere l’esame annuale per la licenza agricola, con $N$ domande vero/falso ($1 \le N \le 1,000,000$). Dopo lo scarso risultato dell’anno scorso, Bessie vuole aiutarlo.
Bessie sa da informazioni interne che il numero di risposte vere è uno fra $t_{1}$, $t_{2}$, $t_{3}$, ..., $t_{K}$ ($0 \le t_i \le N; 0 \le K \le 10,000$), ma non sa la risposta di nessuna domanda specifica. Vuole il miglior punteggio garantito usando attentamente tali informazioni, anche se FJ non conosce alcuna risposta reale.
Considera $N=6$ domande con0 o3 risposte vere. FJ garantisce almeno3 corrette: rispondendo falso a tutte, con0 vere ne azzecca6, con3 vere ne azzecca3. Quindi segnare tutto falso garantisce3 senza conoscere risposte.
Una strategia peggiore indovina3 vere e3 false. Se nessuna è vera, sono corrette le3 segnate false. Se3 sono vere, può azzeccarne0: tutte le3 segnate vere sono false e le altre3 vere. Sebbene tutto falso darebbe3, scegliere3 vere non garantisce neppure1 risposta corretta, dunque nessuna. FJ dovrebbe usare la strategia precedente.
Date le informazioni di Bessie, determina le risposte sempre garantite corrette usandole ottimamente.
Input
- Riga1: due interi separati da spazio $N$ e $K$.
- Righe $2..K+1$: riga $i+1$ contiene un intero $t_{i}$.
Output
- Riga1: un intero, il miglior punteggio garantito a FJ.
Esempi
Input 1
6 2 0 3
Output 1
3
Autore del problema: Tom Conerly, 2010