== include(page="template/taskheader" task_id="placute") ==

Cu ocazia sarbatorilor de iarna, Flamanzila se gandeste ca ar fi momentul sa fure niste porci pentru a isi potoli foamea. Asadar, el gaseste in curtea lui Ionel $N$ porci. Fiecare porc are o placuta de o anumita culoare pe care este inscriptionat numarul de kilograme al acestuia.

Se dau $N$ placute colorate in $K$ culori diferite. Pe fiecare placuta $i$ din cele $N$ este scris un numar natural $a[i]$.

Pentru a se asigura ca Ionel nu observa lipsa porcilor, Flamanzila nu va fura niciodata doi porci consecutivi cu aceeasi culoare a placutei.

Trebuie sa aranjati cele $N$ placute una langa cealalta, in linie, astfel incat sa nu existe doua placute vecine avand aceeasi culoare, iar numerele de pe acestea sa fie in ordine descrescatoare.

De fiecare data cand va veni la furat, Flamanzila va fura cel mai gras porc pe care il va putea fura respectand conditia de mai sus.

Sa se calculeze suma maxima care se poate obtine adunand numerele de pe placute in urma unei astfel de aranjari.

Sa se spuna care este greutatea totala maxima pe care o poate fura Flamanzila, stiind numarul total de porci $N$ si numarul maxim de culori folosite pentru coloararea placutelor $K$.

h2. Date de intrare

În fişierul de intrare $placute.in$ se vor gasi pe prima linie numerele naturale $N$ si $K$. Pe urmatoarele $N$ linii se vor gasi cate 2 numere naturale $g[i]$ si $c[i]$, reprezentand datele porcului $i$ - numarul de kilograme si culoarea placutei $i$.

În fişierul de intrare $placute.in$ se vor gasi pe prima linie numerele naturale $N$ si $K$. Pe urmatoarele $N$ linii se vor gasi cate 2 numere naturale $a[i]$ si $c[i]$, reprezentand numarul inscriptionat si culoarea placutei $i$.

h2. Date de ieşire

În fişierul de ieşire $placute.out$ se va gasi un singur numar natural, reprezentand greutatea maxima pe care o poate fura Flamanzila.

În fişierul de ieşire $placute.out$ se va gasi un singur numar natural, reprezentand suma maxima obtinuta.

h2. Restricţii