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

Poveste şi cerinţă...

 
Între doi stâlpi verticali aflaţi pe malurile unui râu (de o parte şi de alta a râului) se află  legate două cabluri bine întinse, paralele cu solul, având distanţa dintre ele egală cu $d$ centimetri. Cablurile sunt folosite pentru traversarea râului în caz de inundaţii. Stâlpii sunt notaţi cu A şi B, iar cablurile cu 1 şi 2 ca în figura de mai jos. Pe cabluri există desenate câte $n$ puncte colorate cu diverse culori, culorile fiind codificate prin numerele 1, 2, 3,..., $k$. Poziţia punctelor pe fiecare cablu este dată prin distanţa faţă de stâlpul A pentru fiecare punct. Punctele de pe fiecare cablu sunt numerotate cu 1, 2, 3 ,..., $n$. Pe fiecare cablu există cel puţin un punct colorat cu fiecare culoare.  Pentru a uşura deplasarea pe cablu, primarul hotărăşte să lege cu sârmă perechi de puncte de aceeaşi culoare, unul de pe primul cablu, iar celălalt de pe al doilea cablu, astfel încât:
-	pentru fiecare culoare să existe o singură pereche de puncte între care să fie legătură;
-	lungimea totală de sârmă folosită să fie minimă.
 
Să se scrie un program care determină lungimea minimă a sârmei ce va fi folosită pentru rezolvarea problemei şi o mulţime de perechi de puncte ce urmează a fi legate pentru a obţine acest minim.

h2. Date de intrare

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

Fişierul de intrare stalpi.in va conţine:
-	pe prima linie numerele naturale nenule $n$, $d$ separate printr-un spaţiu;
-	pe a doua linie $n$ perechi de numere, formate din distanţa faţă de stâlpul A la fiecare punct şi culoarea asociată punctului, separate prin câte un spaţiu, aflate pe cablul 1;
-	pe a treia linie $n$ perechi de numere, formate din distanţa faţă de stâlpul A la fiecare punct şi culoarea asociată punctului, separate prin câte un spaţiu, aflate pe cablul 2.
 

h2. Date de ieşire

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

Fişierul de ieşire stalpi.out va conţine pe prima linie valoarea minimă cerută, iar pe următoarele $k$ linii numerele de ordine ale punctelor ce vor fi legate cu sârmă, separate printr-un spaţiu, întâi cele de pe cablu 1, urmate de cele de pe cablu 2, în ordinea crescătoare a culorilor.

h2. Restricţii