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

Poveste şi cerinţă...

Citesti tabloidul local, cum faci in fiecare zi. N-ar trebui, dar asta faci. Printre articole:
 
- "Zece optimizari pe care compilatoarele nu vor sa le stii!"
- "Vezi ce olimpic renumit se muta la ASE!"
- "Cautand prin borderouri: ce olimpic si-a inlocuit cafeaua de dimineata cu ... FFT-ul de dimineata."
- "<M-am gandit la viitorul meu si am decis ca este optim sa fac facultatea la UNIBUC si sa ma sustin financiar facand temele celor de la Poli.> Marturisirea cutremuratoare a unui tanar de clasa a 12-a."
- "SONDAJ: Ce se cere mai mult pe piata muncii? Inteligenta, persistenta sau smenul de la Aliens?"
 
Same old. Same old. In schimb, la sectiunea "Barfe despre info-vedete", vezi un articol care te stimuleaza algoritmic:
 
*Alex Velea si iubita au probleme cu.. sosetele?*
 
Renumitul artist-tractorist Alex Velea a fost surprins recent impreuna cu iubita sa cumparand sosete. Dupa cum cititorii nostri stiu prea bine, Alex are o istorie 'complicata':problema/expected cu sosetele. De aceasta data, Alex doreste sa cumpere $P$ tipuri de sosete dintre cele $N$ disponibile la magazinul ales. Fiecare tip este definit de doi parametri: culoarea si marimea. Gurile rele spun ca iubita lui Alex ii impune o restrictie.. neobisnuita achizitiei sale. Ea stie ca Alex este foarte nepasator atunci cand isi imbraca sosetele. Mai exact, pentru Alex este acceptabil sa imbrace doua sosete daca acestea au aceeasi marime *sau* aceeasi culoare. Prietena lui Alex numeste o pereche in care sosetele au aceeasi marime *sau* aceeasi culoare dar *nu au* aceeasi marime *si* aceeasi culoare ca fiind "ciudata".
 
Ea ar dori ca Alex sa-si cumpere $P$ tipuri de sosete astfel incat numarul total de perechi de tipuri de sosete ciudate formate sa fie minim posibil. Ea vrea raspunsul pentru fiecare $P$ de la $1$ la $K$.
 

h2. Date de intrare

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

Fişierul de intrare $socks.in$ va contine pe prima sa linie numerele $N$ si $K$, reprezentand numarul de tipuri de sosete disponibile, respectiv limita superioara a $P$-ului pentru care prietena lui Alex vrea sa afle raspunsul.
Urmatoarele $N$ linii vor contine o pereche $culoare marime$, culoare fiind un sir de caractere, iar marime este un numar natural.

h2. Date de ieşire

În fişierul de ieşire $socks.out$ ...

În fişierul de ieşire $socks.out$ se vor afla $K$ linii, a $i$-a continand raspunsul pentru $P = i$.

h2. Restricţii

* $1 ≤ N, K ≤ 1000$

* $1 ≤ K ≤ N ≤ 1000$
* $1 ≤ Marimile sosetelor ≤ 10^9^$
* $Culorile sosetelor sunt siruri de caractere de lungime maxim 20, fara spatii$.
* $Toate cele N tipuri de sosete disponibile sunt distincte doua cate doua (difera fie marimea, fie culoarea, fie ambele).$

h2. Exemplu
table(example). |_. socks.in |_. socks.out |
| 3 3

Rosu 45

Nelachet 45

Lachet 43
Lachet 45
| 0

h3. Explicaţie

...

Pentru $P = 1$ Alex poate cumpara oricare dintre cele trei tipuri de sosete.
Pentru $P = 2$ Alex va cumpara tipurile $1$ si $2$, care au atat culorile cat si marimile distincte. Astfel, nu va face nicio pereche ciudata.
Pentru $P = 3$ Alex va fi obligat sa cumpere si al treilea tip de sosete. Acesta formeaza o pereche ciudata cu tipul $1$ (deoarece au aceeasi marime, dar culori diferite) si cu tipul $2$ (deoarece au aceeasi culoare, dar marimi diferite). Astfel, raspunsul este $2$.

== include(page="template/taskfooter" task_id="socks") ==