Fişierul intrare/ieşire:	stalpi3.in, stalpi3.out	Sursă	ONI 2011, clasa a 9-a
Autor	Doru Popescu Anastasiu	Adăugată de	Eugenie Daniel Posdarascu •eudanip
Timp execuţie pe test	0.05 sec	Limită de memorie	8192 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Stalpi3

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

Date de intrare

Fişierul de intrare stalpi3.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.

Date de ieşire

Fişierul de ieşire stalpi3.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. 

Restricţii

• 1 ≤ N ≤ 10000
• 1 ≤ K ≤ 100
• 1 ≤ D ≤ 1000
• Distanţa dintre cei doi stâlpi A şi B este 30000.
• Distanţele de la stâlpul A la puncte sunt numere naturale.
• Distanţa minimă va fi afişată trunchiată la primele 3 zecimale.
• Toate punctele de pe un cablu sunt distincte.
• Se acordă 40% din punctaj pentru determinarea corectă a minimului din cerinţă.

Exemplu

Explicaţie

Sunt N=3 perechi de puncte, K=2 culori, codificate cu 1 şi 2.
Necesarul minim de sârmă este 211.803.
Se leagă punctul P3 de punctul Q2 (ambele au culoarea 1).
Se leagă punctul P2 de punctul Q1 (ambele au culoarea 2).
Exemplul corespunde imaginii de mai jos.

Cum se trimit solutii?