== include(page="template/taskheader" task_id="placute") ==
Se dau $N$ placute colorate in $K$ culori diferite. Pe fiecare placuta $i$ din cele $N$ este scris un numar natural $a[i]$.
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.
Trebuie sa aranjati cele $N$ placute una langa cealalta, in linie, astfel incat sa nu existe doua placute vecine avand aceeasi culoare.
Pentru a se asigura ca Ionel nu observa lipsa porcilor, Flamanzila nu va fura niciodata doi porci consecutiv care au aceeasi culoare a placutei.
Dintre toate aranjarile posibile, sa se afiseze cea care are suma numerelor de pe placutele folosite maxima.
De fiecare data cand va veni la furat, Flamanzila va fura cel mai gras porc pe care il va gasi in curtea lui Ionel, respectand conditia de mai sus.
Daca exista mai multe solutii, se poate afisa oricare dintre acestea.
Sa se spuna care este greutatea totala maxima pe care o poate fura Flamanzila, stiind numarul total de porci, $N$, si numarul 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 $a[i]$ si $c[i]$, reprezentand numarul inscriptionat 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 $g[i]$ si $c[i]$, reprezentand datele pentru porcul $i$ - numarul de kilograme si culoarea placutei lui.
h2. Date de ieşire
În fişierul de ieşire $placute.out$ se va afisa pe prima linie suma maxima obtinuta.
În fişierul de ieşire $placute.out$ se va gasi un singur numar natural, reprezentand greutatea totala maxima pe care o poate fura Flamanzila.
h2. Restricţii
* $1 ≤ N ≤ 100000$
* $1 ≤ K ≤ 1000$
* $1 ≤ a[i] ≤ 1000$
* $1 ≤ g[i] ≤ 1000000$
* $1 ≤ c[i] ≤ K$
* $Ionel nu are 2 porci cu aceeasi greutate.$
h2. Exemplu
table(example). |_. placute.in |_. placute.out |
| d
| d
| 5 3
5 1
4 3
1 2
2 2
3 2
| 12
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="placute") ==
== include(page="template/taskfooter" task_id="placute") ==
