Î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ă.
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 stalpi2.in va conţine pe prima linie numerele naturale nenule n, d separate printr-un spaţiu. Pe a doua linie se află 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 se află 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 stalpi2.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 cablul 1, urmate de cele de pe cablul 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ţă.
Exemple
stalpi2.in
stalpi2.out
Explicaţii
3 100
50 1 200 2 100 1
250 2 100 1 300 2
211.803
3 2
2 1
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).
