Cerința

Alex s-a decis să organizeze pentru colegii lui un concurs de orientare turistică, pe care l-a intitulat “Treasure Hunt”, nu pentru că ar fi avut ceva bogății de ascuns, ci pentru a-i face curioși și a-i mobiliza să mai lase puțin joaca pe calculator și să facă mișcare în aer liber. Pentru aceasta el a cercetat terenul pe care s-a decis să organizeze acest concurs și a identificat n puncte posibile de amplasare a posturilor de control, prin care concurenții să treacă obligatoriu și de unde să primească indicii referitoare la următorul punct. Bineînțeles că în punctele de control există și “comori” ascunse, care au asociate anumite punctaje, de valori cunoscute. A notat pe o hartă coordonatele (x,y) ale acestor puncte, în ordinea necesară parcurgerii lor, dar și altitudinea la care se află acestea și punctajul p atribuit “comorii” din acel punct. Problema a apărut mai târziu, atunci când Alex s-a decis să nu lase un concurent să se oprească în toate punctele, pentru că atunci colegii lui ar găsi un motiv să mai tragă de timp pentru a se odihni și concursul ar dura prea mult. Așa că a stabilit să permită maxim M opriri din cele N puncte, cu condiția ca între două opriri succesive distanța de pe traseu să nu fie mai mică decât o valoare impusă, d, stabilită de Alex printr-o metodă proprie. Trecerea prin toate punctele este obligatorie, așa că distanța se calculează ca suma distanțelor dintre puncte. Curios din fire, Alex vrea să știe:

• Care este efortul total pentru parcurgerea întregului traseu și care este distanța maximă între două puncte de pe traseu. Efortul trebuie calculat după o formulă pe care tot Alex a stabilit-o ca suma eforturilor de pe fiecare tronson în parte, definit astfel
  \( e =
  \begin{cases}
  𝑑 + 𝑑 ∗ ∆ℎ/10 & \text {, 𝑑𝑎𝑐a 𝑢𝑟𝑐a} \\
  𝑑 + 𝑑 ∗\frac{|∆ℎ|}{5∗10} & \text{, 𝑑𝑎𝑐a 𝑐𝑜𝑏𝑜𝑎𝑟a} \\
  \end{cases} \), unde ∆ℎ este diferența de altitudine dintre două puncte consecutive de pe traseu, chiar dacă în acestea concurentul nu se oprește.
• Care este punctajul maxim pe care îl poate obține un concurent, și care ar trebui să fie punctele de control în care să se oprească pentru a le obține. Din păcate Alex nu e prea bun la informatică, așa ca vă roagă pe voi să-l ajutați.

Date de intrare

Fișierul treasurehunt.in și are următoarea formă:

• Pe prima linie un număr natural z=1 sau z=2.
• Pe următoarea linie numerele N, M și d, reprezentând numărul de puncte de control stabilite, numărul maxim de opriri acceptate, respectiv distanța minimă între două opriri succesive.
• Pe următoarele N linii câte 4 numere x, y, h, p reprezentând coordonatele, altitudinea și punctajul comorii din fiecare punct. Punctele 1 și n vor rămâne obligatoriu pe traseu și nu conțin comori, așadar nu li se impune nici o condiție dintre cele stabilite mai sus (nu se numără în cele M opriri, iar distanța față de punctele unei opriri alese poate fi mai mica decât d).

Date de ieșire

Fișierul treasurehunt.out are forma:

• Dacă z=1, pe prima linie un număr real care reprezintă distanța maximă între două puncte de pe traseul inițial şi pe a doua linie un alt număr real care reprezintă efortul total pentru parcurgerea întregului traseu.
• Dacă z=2, pe prima linie punctajul maxim care poate fi obținut cu cel mult M opriri şi pe următoarea linie numerele de ordine ale punctelor de pe traseu unde se fac opririle corespunzătoare acestui caz.

Restricții și precizări

• 1 ≤ M ≤ N ≤ 10000
• 0 ≤ p ≤ 100
• 0 <= d <= 1000
• Coordonatele punctelor și altitudinea sunt numere întregi cu maxim 4 cifre, distanțele și efortul sunt numere reale calculate cu exact 2 cifre, fără aproximare.

Exemplul 1:

treasurehunt.in

1
10 5 3
0 0 0 0
2 0 3 4
3 0 3 7
4 0 5 10
5 0 5 5
6 0 3 9
7 0 4 10
8 0 4 15
10 0 6 15
15 0 0 0

treasurehunt.out

5
16.94

Explicație

Între punctele 1 și 2 distanța este 2 și urcă cu 3, deci efortul va fi 2+2*3/10=2.6 . Între punctele 2 și 3 distanța este 1 și ∆ℎ = 0, deci efortul va fi 1. Între punctele 3 și 4 distanța este 1 și ∆ℎ =2, deci efortul va fi 1,2. Între punctele 4 și 5 distanța este 1 și ∆ℎ = 0, deci efortul va fi 1, etc., rezultă efortul total 16.94. Distanta maxima este 5 intre punctele 9 și 10

Exemplul 2:

treasurehunt.in

2
10 5 3
0 0 0 0
2 0 3 4
3 0 3 7
4 0 5 10
5 0 5 5
6 0 3 9
7 0 4 10
8 0 4 15
10 0 6 15
15 0 0 0

treasurehunt.out

35
1 4 7 9 10

Explicație

Punctajul maxim care se poate obține este 35, când concurenții se opresc în punctele 1,4,7,9 și 10 din care obțin punctajele 0+10+10+15+0.