stalpi

Î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, \ldots, 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, \ldots, 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:

Figura 1 din enunțul original al problemei stalpi.Mărește schema ↗

• 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ă

Cerință

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

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.

Restricții și precizări

• $1 \leq n \leq 10 \ 000$
• $1 \leq k \leq 100$
• $1 \leq d \leq 1 \ 000$
• Distanţa dintre cei doi stâlpi $A$ şi $B$ este $30 \ 000$
• 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

stalpi.in

3 100
50 1 200 2 100 1
250 2 100 1 300 2

stalpi.out

211.803
3 2
2 1

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