== include(page="template/taskheader" task_id="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ă.
Î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 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.
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$.
h2. Date de ieşire
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.
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.
h2. 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ţă.
h2. Exemplu
table(example). |_. stalpi3.in |_. stalpi3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|3 100
50 1 200 2 100 1
250 2 100 1 300 2
|211.803
3 2
2 1
|
h3. 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.
!problema/stalpi3?stalpi.jpg!
== include(page="template/taskfooter" task_id="stalpi3") ==
