Scrieti un program care sa determine efortul minim necesar pentru a urca pe o scara construita conform restrictiilor problemei, precum si o modalitate de a construi scara care va fi urcata cu efort minim.

h2. Date de intrare

Fisierul de intrare $scara2.in$ va contine pe prima linie 4 numere naturale separate prin cate un spatiu $H$ $N$ $M$ $P$ (cu semnificatia din enunt).

Fisierul de intrare $scara2.in$ va contine pe prima linie $4$ numere naturale separate prin cate un spatiu $H$ $N$ $M$ $P$ (cu semnificatia din enunt).

h2. Date de iesire
Fisierul de iesire $scara2.out$ va contine:

* 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 reprezinta inaltimile celor N trepte ale scarii (in ordinea de la sosea catre vila), separate prin cate un spatiu.
 

* 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 reprezinta inaltimile celor $N $ trepte ale scarii (in ordinea de la sosea catre vila), separate prin cate un spatiu.

h2. Restrictii

* $0< $H$ &le; 75.$
* $0< $N$ &le; 8.$

* $0 < $H$ &le; 75.$
* $0 < $N$ &le; 8.$

* $0 ≤ $P$ ≤ 10.$

* $0< $M$ &le; 14.$
* $Pentru datele de test, problema are intodeauna solutie.$
* $Daca exista mai multe solutii (modalitati de a construi scara astfel incat sa obtineti efortul minim dorit), veti afisa prima solutie in ordine lexicografica.$
* $Spunem ca vectorul x=(x1, x2, ..., xk) preceda in ordine lexicografica vectorul y=(y1, y2, ..., yk) daca exista i>0 astfel incat xj=yj, pentru orice j<i si xi<yi.$
* $Nu se acorda punctaje partiale.$

* $0 < $M$ &le; 14.$
* Pentru datele de test, problema are intodeauna solutie.
* Daca exista mai multe solutii (modalitati de a construi scara astfel incat sa obtineti efortul minim dorit), veti afisa prima solutie in ordine lexicografica.
* Spunem ca vectorul $x=(x1, x2, ..., xk)$ preceda in ordine lexicografica vectorul $y=(y1, y2, ..., yk)$ daca exista $i>0$ astfel incat $xj=yj$, pentru orice $j<i$ si $xi<yi.$
* Nu se acorda punctaje partiale.

h2. Exemplu