Rezolvare PBinfo #4470

Cerința

Un elev dispune de n cuburi, pentru fiecare cub cunoscându-se latura sa c[i]. El dorește să construiască m turnuri, fiecare turn conținând doar cuburi de aceeași dimensiune. Să se determine înălțimea maximă care se poate obține pentru fiecare din cele m turnuri.

Date de intrare

Programul citește de la tastatură numărul n, numărul de cuburi. Pe a doua linie se găsesc n valori naturale în ordine crescătoare, separate prin câte un spațiu, reprezentând dimensiunea cuburilor. Pe următorul rând se găsește valoarea m, reprezentând numărul de turnuri care trebuie construite. Pe următorul rând se găsesc m valori naturale, separate prin câte un spațiu reprezentând dimensiunea cubului folosit la construirea turnului.

Date de ieșire

Programul va afișa pe ecran numărul m numere naturale, separate prin câte un spațiu, înălțimea ma ximă care se poate obține pentru fiecare turn.

Restricții și precizări

• 1 ≤ n, m ≤ 100.000
• cele n numere citite de pe al doilea rând vor fi numere naturale nenule mai mici ca 1.000.000.000
• valorile de pe ultimul rând sunt cuprinse între 1 și 1.000.000.000;
• dacă nu există niciun cub de dimensiunea cerută, atunci înălțimea turnului care se poate construi este 0;
• după construirea unui turn, cuburile se pun la loc și pot fi folosite la construirea altui turn;
• pentru teste în valoare de 30 de puncte 1 ≤ n, m ≤ 1000;
• pentru alte teste în valoare de 30 de puncte 1 ≤ c[i] ≤ 1.000.000

Exemplu:

Intrare

10
1 3 3 3 5 6 6 8 8 8
4
6 4 5 3

Ieșire

12 0 5 9

Explicație

Se vor construi 4 turnuri.
La construirea primului turn se folosesc cuburi cu latura 6. Înălțimea maximă a turnului este 12.
Al doilea turn trebuie construit cu cuburi de dimensiune 4. Nu există asemenea cuburi, înălțimea turnului va fi 0.
La al treilea turn se folosesc cuburi de latură 5. Există un singur cub cu această dimensiune, deci înălțimea va fi 5.
Ultimul turn va avea înălțimea 9, deoarece conține 3 cuburi de latură 3.