Ion a plecat la pescuit. În zona în care el pescuieşte există n lacuri. Toate lacurile sunt plasate pe marginea aceleiaşi şosele şi sunt numerotate de la 1 la n în ordinea în care sunt amplasate pe şosea. El are la dispoziţie pentru pescuit h ore şi se află iniţial la lacul cu numărul 1. Ion poate vizita lacurile exact în ordinea în care sunt amplasate pe şosea, dar nu se opreşte să pescuiască decât dacă doreşte şi poate să termine pescuitul la oricare lac doreşte.
Ion face sportul acesta frecvent şi cunoaşte ti (i=1, 2, ..., n-1) numărul de intervale de câte 5 minute care îi sunt necesare pentru a ajunge de la lacul i la lacul i+1.
De asemenea, Ion cunoaşte bine lacurile din zonă şi a determinat pentru fiecare lac i numărul de peşti fi pe care el se aşteaptă să îi prindă în primele 5 minute din lacul i. La fiecare 5 minute, numărul de peşti pe care el se aşteaptă să îi prindă în interval de 5 minute din lacul i va scădea cu o rată constantă di. Dacă numărul de peşti pe care el se aşteaptă să îi prindă în următorul interval este <=di, deduce că nu mai există peşti în lacul i pe care ar putea să îi prindă în următorul interval.
Pentru a simplifica problema, Ion presupune că nu mai pescuieşte nimeni în zonă în acelasi timp cu el, deci că previziunile sale sunt exacte.

Cerinţă

Scrieţi un program care să determine numărul maxim de peşti pe care Ion îi poate pescui, precum şi modul în care Ion îşi planifică pescuitul pentru a obţine un număr maxim de peşti.

Date de intrare

Fişierul de intrare peste.in conţine mai multe seturi de date de test.
Fiecare set de date de test conţine pe prima linie un număr natural n care reprezintă numărul de lacuri. Pe cea de a doua linie se află un număr natural h care reprezintă numărul de ore pe care Ion le are la dispoziţie. Pe cea de a treia linie sunt n numere naturale separate prin câte un spaţiu f1 f2 ... fn care reprezintă numărul de peşti pe care Ion se aşteaptă să îi prindă în primele 5 minute din fiecare lac. Pe cea de a patra linie se află n numere naturale separate prin câte un spaţiu d1 d2 ... dn care reprezintă rata cu care scade după fiecare interval de 5 minute numărul de pesti ce poate fi pescuit în următorul interval de 5 minute din fiecare lac. Pe ultima linie se află n-1 numere naturale separate prin câte un spaţiu t1 t2...tn-1 care reprezintă numărul de intervale de 5 minute necesare pentru a ajunge de la un lac la următorul. Fişierul de intrare se încheie cu o linie care conţine valoarea 0.

Date de ieşire

Fişierul de ieşire peste.out va conţine câte două linii pentru fiecare set de date de intrare. Pe prima dintre aceste două linii, va fi afişat numărul maxim de peşti ce poate să îi pescuiască Ion. Pe cea de a doua linie vor fi afişate n numere naturale separate prin câte un spaţiu. Al i-lea număr de pe linie reprezintă numărul de minute pe care la petrece Ion pescuind din lacul i. Numărul de minute pe care Ion îl petrece la fiecare lac trebuie să fie multiplu de 5.
Dacă există mai multe soluţii (posibilităţi de a planifica pescuitul astfel încât să se obţină un număr maxim de peşti) se va alege soluţia în care timpul petrecut la lacul 1 este maxim. Dacă în continuare există mai multe soluţii, va fi aleasă cea în care timpul petrecut la lacul 2 este maxim, etc.

Restricţii

1<=h<=16
2<=n<=25
0<ti<=192
0<=fi
0<=di

Exemple

peste.in	peste.out
2 1 10 1 2 5 2 4 4 10 15 20 17 0 3 4 3 1 2 3 4 4 10 15 50 30 0 3 4 3 1 2 3 0	31 45 5 480 240 0 0 0 724 115 10 50 35

autor: Prof. Emanuela Cerchez

propunător: Prof. Emanuela Cerchez

Liceul de Informatica ″Grigore Moisil″

emanuela.cerchez@gmail.com