== include(page="template/taskheader" task_id="caramizi") ==
Poveste şi cerinţă...
Haralambie s-a decis sa incerce o noua afacere in domeniul constructiilor. A procurat deja $N$ tipuri de caramizi de dimensiuni identice dar de culori diferite, din fiecare tip existand $C{~i~}$ caramizi. El va aseza caramizi unele peste altele pentru a construi turnuri dupa urmatoarele reguli:
# Fiecare turn trebuie sa contina doar caramizi de culori diferite.
# Toate turnurile trebuie sa aiba aceeasi inaltime.
Scopul pe care si-l propune Haralambie este de a folosi cat mai multe caramizi in constructiile sale. Nefiind pasionat de informatica, se bazeaza pe voi sa ii raspundeti la $M$ intrebari de tipul: _"Care este numarul maxim de caramizi pe care il pot folosi pentru a construi cel mult $L{~i~}$ turnuri?"_. In afara de glorie, Haralambie va asigura ca o sa va ofere si caramizile ramase.
h2. Date de intrare
Fişierul de intrare $caramizi.in$ ...
Fişierul de intrare $caramizi.in$ va contine pe prima linie numerele $N$ si $M$ cu semnificatiile din enunt. Pe urmatoarea linie se vor afla $N$ numere naturale $C{~1~}$, $C{~2~}$ ... $C{~$N$~}$, reprezentand numarul de caramizi din fiecare tip. Pe ultima linie se vor afla $M$ numere $L{~1~}$, $L{~2~}$, ..., $L{~$M$~}$, cu semnificatia din enunt.
h2. Date de ieşire
În fişierul de ieşire $caramizi.out$ ...
În fişierul de ieşire $caramizi.out$ se vor afla $M$ linii, fiecare continand raspunsul la intrebarea corespunzatoare din fisierul de intrare.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 200 000$
* $1 ≤ M ≤ 200 000$
* $1 ≤ C{~i~} ≤ 1 000 000$
* $1 ≤ L{~i~} ≤ 2 000 000 000$
* Pentru $30%$ din testele folosite la evaluare $1 ≤ N ≤ 100$, $1 ≤ M ≤ 100$, $1 ≤ C{~i~} ≤ 100$, $1 ≤ L{~i~} ≤ 100$.
* Pentru alte $20%$ din testele folosite la evaluare $1 ≤ N ≤ 500$, $1 ≤ M ≤ 5 000$, $1 ≤ C{~i~} ≤ 100$, $1 ≤ L{~i~} ≤ 5 000$.
* Pentru alte $30%$ din testele folosite la evaluare $1 ≤ L{~i~} ≤ 1 000 000$.
* Pentru afisarea rezultatelor se recomanda folosirea intregilor cu semn pe $64$ de biti.
h2. Exemplu
table(example). |_. caramizi.in |_. caramizi.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 5
4 7 10 11 13
3 12 13 14 21
| 15
40
40
42
45
|
h3. Explicaţie
...
In primul caz, Haralambie construieste $3$ turnuri, fiecare continand toate cele $5$ tipuri de caramizi, aranjate oricum. Urmatoarele doua cazuri au aceeasi solutie, in care Haralambie construieste $10$ turnuri de cate $4$ caramizi fiecare. In al patrulea caz, Haralambie va folosi un numar maxim de caramizi construind $14$ turnuri de cate $3$ caramizi fiecare. In ultimul caz, Haralambie poate folosi toate caramizile pe care le are la dispozitie.
== include(page="template/taskfooter" task_id="caramizi") ==
