munte

Într-o zonă montană se doreşte deschiderea unui lanţ de telecabine. Staţiile de telecabine pot fi înfiinţate pe oricare din cele $N$ vârfuri ale zonei montane. Vârfurile sunt date în ordine de la stânga la dreapta şi numerotate de la $1$ la $N$, fiecare vârf $i$ fiind precizat prin coordonata $X_i$ pe axa OX şi prin înălţimea $H_i$.

Se vor înfiinţa exact $K$ staţii de telecabine. Staţia de telecabine $i$ va fi conectată cu staţiile $i-1$ şi $i+1$; staţia $1$ va fi conectată doar cu staţia $2$, iar staţia $K$, doar cu staţia $K-1$. Staţia $1$ va fi obligatoriu amplasată în vârful $1$, iar staţia $K$ în vârful $N$.

Se doreşte ca lanţul de telecabine să asigure legătura între vârful $1$ şi vârful $N$. Mai mult, se doreşte ca lungimea totală a cablurilor folosite pentru conectare să fie minimă. Lungimea cablului folosit pentru a conecta două staţii este egală cu distanţa dintre ele. În plus, un cablu care uneşte două staţii consecutive nu poate avea lungimea mai mare decât o lungime fixată $L$.

O restricţie suplimentară este introdusă de formele de relief. Astfel, vârfurile $i$ şi $j$ ($i < j$) nu pot fi conectate direct dacă există un vârf $v$ ($i < v < j$) astfel încât segmentul de dreapta care ar uni vârfurile $i$ şi $j$ nu ar trece pe deasupra vârfului $v$. În cazul în care cele trei vârfuri sunt coliniare, se consideră toate trei ca fiind staţii, chiar dacă distanţa dintre vârfurile $i$ şi $j$ este mai mică decât $L$.

Cerinţă

Dându-se amplasarea celor $N$ vârfuri ale lanţului muntos, stabiliţi o modalitate de dispunere a celor $K$ staţii de telecabine astfel încât lungimea totală a cablurilor folosite pentru conectare să fie minimă, cu restricţiile de mai sus.
Se garantează că, pe toate testele date la evaluare, conectarea va fi posibilă.

Date de intrare

Prima linie a fişierului de intrare munte.in conţine trei numere întregi $N$, $K$ şi $L$, separate prin spaţii, cu semnificaţiile de mai sus. Următoarele $N$ linii conţin coordonatele vârfurilor; linia $i+1$ conţine coordonatele vârfului $i$, $X_i$ şi $H_i$, separate printr-un spaţiu.

Date de ieșire

În fişierul munte.out veţi afişa:

• pe prima linie lungimea totală minimă a cablurilor, rotunjită la cel mai apropiat numar întreg (pentru orice întreg $Q$, $Q.5$ se rotunjeste la $Q+1$);
• pe a doua linie $K$ numere distincte între $1$ şi $N$, ordonate crescător, numerele vârfurilor în care se vor înfiinţa staţii de telecabine. Dacă există mai multe variante, afişaţi una oarecare.

Restricții și precizări

• $2 \leq N \leq 100$
• $2 \leq K \leq 30$ şi $K \leq N$
• $0 \leq L, X_i, H_i \leq 100 \ 000$ şi $X_i < X_{i+1}$

Exemplu

munte.in

7 5 11
0 16
4 3
6 8
7 4
12 16
13 16
14 16

munte.out

22
1 3 5 6 7

Explicație

• trasarea unui cablu direct între vârfurile $1$ şi $5$ ar fi contravenit restricţiei referitoare la lungimea maximă a unui cablu; în plus, s-ar fi obţinut o soluţie cu $2$ staţii de telecabine în loc de $3$ (deci soluţia ar fi invalidă şi pentru valori mari ale lui $L$);
• pentru a ilustra restricţia introdusă de formele de relief, precizăm că vârfurile $1$ şi $4$ nu au putut fi conectate direct datorită înălţimii vârfului $3$. De asemenea, vârfurile $5$ şi $7$ nu au putut fi conectate direct datorită înălţimii vârfului $6$.