== 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]$.
 
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.

Poveste şi cerinţă...

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

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

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

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 |

| d
| d

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

|
h3. Explicaţie