Scara

Ion şi-a construit o vilă pe frumosul vârf al unui munte. Acum proiectează o scară specială, pe care va urca de la şosea până la vilă. Diferenţa de nivel dintre şosea şi vilă este $H$ (deci aceasta trebuie să fie înălţimea totală a scării). Scara va avea $N$ trepte, toate de aceeaşi lăţime, dar de înălţimi distincte două câte două.

Ion a sesizat că efortul pe care îl depune pentru a urca o treaptă este egal cu înălţimea treptei. Dar dacă el urcă $x$ trepte deodată, efortul depus este egal cu media aritmetică a înălţimilor acestor $x$ trepte pe care le urcă deodată + un efort de valoare constantă $p$ (necesar pentru a-şi lua avânt).

Fiind un tip atletic, Ion poate urca mai multe trepte deodată, dar suma înălţimilor treptelor urcate deodată nu trebuie să depăşească o valoare maximă $M$.

Cerinţă

Scrieţi un program care să determine efortul minim necesar pentru a urca pe o scară construită conform restricţiilor problemei, precum şi o modalitate de a construi scara care va fi urcată cu efort minim.

Date de intrare

Fişierul de intrare scara.in va conţine pe prima linie $4$ numere naturale separate prin câte un spaţiu $H \ N \ M \ p$ (cu semnificaţia din enunţ).

Date de ieșire

Fişierul de ieşire scara.out va conţine

• pe prima linie va fi scris efortul minim necesar (cu $2$ zecimale cu rotunjire);
• pe cea de a doua linie vor fi scrise $N$ numere naturale nenule care reprezintă înălţimile celor $N$ trepte ale scării (în ordinea de la şosea către vilă), separate prin câte un spaţiu.

Restricții și precizări

• $0 < H \leq 75$
• $0 < N \leq 8$
• $0 < M < 14$
• $0 \leq p \leq 10$
• Pentru datele de test, problema are întodeauna soluţie.
• Dacă există mai multe soluţii (modalităţi de a construi scara astfel încât să obţineţi efortul minim dorit), veţi afişa prima soluţie în ordine lexicografică.
• Spunem că vectorul $x=(x_1, x_2, ..., x_k)$ precedă în ordine lexicografică vectorul $y=(y_1, y_2, ..., y_k)$ dacă există $i \geq 1$ astfel încât $x_j=y_j$, pentru orice $j<i$ şi $x_i<y_i$.
• Dacă a doua zecimală a efortului minim este $0$, sau chiar ambele zecimale sunt $0$ nu este necesar să le afişaţi. Deci în exemplu s-ar fi putut scrie efortul minim $9$ sau $9.0$.
• Se acordă $40\%$ din punctaj pentru prima cerinţă (efortul minim).
• Dacă efortul minim este corect şi se afişează şi o soluţie corectă (care respectă restricţiile problemei şi corespunde efortului minim), dar această soluţie nu este prima din punct de vedere lexicografic, se obţine $80\%$ din punctaj. Pentru rezolvarea corectă şi completă a ambelor cerinţe se obţine $100\%$ din punctaj.

Exemplu

scara.in

10 4 5 2

scara.out

9.00
1 4 2 3