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

Poveste şi cerinţă...

Se dau $N$ placute colorate in $K$ culori diferite. Pe fiecare placuta $i$ din cele $N$ este scris un numar natural $a[i]$.
 
Trebuie sa aranjati cele $N$ placute una langa cealalta, in linie, astfel incat sa nu existe doua placute vecine avand aceeasi culoare.
 
Dintre toate aranjarile posibile, sa se afiseze cea care are suma numerelor de pe placutele folosite maxima.
 
Daca exista mai multe solutii, se poate afisa oricare dintre acestea.

h2. Date de intrare

Fişierul de intrare $placute.in$ ...

Î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$ ...

În fişierul de ieşire $placute.out$ se va afisa pe prima linie suma maxima obtinuta.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100000$
* $1 ≤ K ≤ 1000$
* $1 ≤ a[i] ≤ 1000$
* $1 ≤ c[i] ≤ K$

h2. Exemplu
table(example). |_. placute.in |_. placute.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| d
| d

|
h3. Explicaţie