Canaste

Pasionat de jocurile de cărți în echipă, marele Idum a început să se antreneze de unul singur pentru ele. Unul din jocurile lui preferate se numește canastă, joc în care o parte semnificativă din strategie se învârte în jurul obținerii canastelor: grupe de șapte ($7$) cărți care au aceeași valoare, sau în completare jokeri. O proprietate necesară a canastelor este aceea că fiecare canastă conține mai multe valori în componența ei decât jokeri, cu excepția canastelor formate doar din jokeri. Pentru a se antrena eficient, Idum se concentrează pe trei scenarii diferite pe un pachet de $N$ cărți:

1. Date fiind cele $N$ cărți de joc, care este numărul maxim de canaste posibile?
2. Date fiind cele $N$ cărți de joc și știind că toate canastele formate din valori de $1$ (putând conține și jokeri, dar neapărat valori de $1$) vor valora două puncte, iar celelalte canaste un singur punct, care este punctajul maxim posibil?
3. Date fiind cele N cărți de joc și știind că toate canastele formate din jokeri vor valora $3$ puncte, cele din valori de $1$ (putând conține și jokeri, dar neapărat valori de $1$) vor valora două puncte, iar celelalte canaste un singur punct, care este punctajul maxim posibil?

Cerință

Imud, fiind obosit după numărarea celor $N$ cărți de joc și transcrierea lor pe calculator, vă roagă să îl ajutați cu răspunsurile pentru cele trei scenarii date.

Date de intrare

Datele de intrare conțin, pe prima linie, două valori:

• $N$, numărul de cărți de joc din pachetul dat;
• $C$, un număr de la $1$ la $3$, ce reprezintă numărul cerinței pentru acest test.

Pe următoarea linie urmează cele $N$ cărți de joc, fiecare descrisă printr-o valoare $V_i$ care poate fi:

• nenulă, reprezentând valoarea cărții de joc cu indicele $i$,
• sau $0$, în cazul în care cartea cu numărul $i$ este un joker.

Date de ieșire

Afișați răspunsul pentru scenariul dat pe o linie.

Restricții

• $2 \leq n \leq 100 \ 000$;
• $1 \leq C \leq 3$;
• $0 \leq V_i \leq 100 \ 000 \ \forall 1 \leq i \leq N$, unde jokerii sunt marcați cu $0$;
• Vom nota cu $J$ numărul jokerilor din test.

Exemplul 1

stdin

22 1
1 1 0 0 1 1 0 1 2 2 2 1 1 2 3 3 3 0 0 0 0 1

stdout

2

Explicație

$C=1$, deci ne interesează numărul maxim de canaste posibile. Putem crea o canastă de $1$ fără să folosim jokeri, și una de $2$ folosind trei jokeri. Nu putem crea o canastă de $3$ folosind patru jokeri, deoarece aceasta ar avea mai mulți jokeri decât valori, lucru care nu este permis. O altă soluție pentru două canaste ar fi să avem o canastă numai din $1$ și una numai din jokeri. O a treia soluție ar fi să avem două canaste, fiecare cu câte patru de $1$ si câte trei jokeri.

Exemplul 2

stdin

24 2
1 4 1 4 4 0 0 1 1 4 0 0 0 3 3 2 2 2 2 2 3 3 4 3

stdout

3

Explicație

$C=2$, deci ne interesează scorul maxim când canastele de $1$ sunt mai valoroase. Putem crea o canastă de $1$ cu trei jokeri, și una de $2$ folosind doi jokeri, pentru scorul total de 3. O altă soluție ar fi să avem o canastă din $2$ și una din $3$, fiecare cu câte doi jokeri, pentru un scor de $2$.

Exemplul 3

stdin

25 3
1 1 0 0 1 1 0 1 2 2 2 1 1 2 3 3 3 0 0 0 0 1 0 0 0

stdout

6

Explicație

$C=3$, deci ne interesează scorul maxim când canastele de $1$ și de jokeri sunt mai valoroase. Putem crea o canastă de $1$ fără să folosim jokeri, și una de $2$ folosind trei jokeri, pentru scorul total de 3. O altă soluție (mai bună) ar fi să avem o canastă numai din $1$ și una numai din jokeri, alături de o canastă cu patru de $2$ și $3$ jokeri, pentru un scor total de $6$.