Simulare Lot 2018 Baraj 4 Juniori | panou

Gigel vrea să-şi deschidă o firmă de publicitate. Întrucât nu are experienţă, s-a decis să înceapă modest închiriind $Q$ panouri publicitare, din care la randul lui va închiria anumite porţiuni. Astfel el s-a decis să divizeze fiecare panou de înălţime $H$ într-un număr maxim posibil de regiuni/benzi orizontale, toate de înălţime $h$, deci identice, cu condiţia să nu se suprapună. De asemenea, el a făcut o analiză a pieţei şi a asociat profitul $P_h$ ce l-ar putea obţine pentru o regiune de înălţime $h$, $1 \leq h \leq h_{max}$. Întrucât fiecare client are propria opinie despre dimensiunea reclamei perfecte, profiturile nu sunt corelate cu dimensiunile, astfel fiind posibil ca regiuni mai mici să genereze profit mai mare.

Cerinţa

Cunoscând secvenţa profiturilor, $P_1$, $P_2$, $\dots$, $P_{h_{max}}$, Gigel îşi doreşte să afle pentru o listă de panouri $H_1$, $H_2$, $\dots$, $H_Q$ care vor fi profiturile maxime asociate.

Date de intrare

Fişierul de intrare panou.in conţine pe prima linie $h_{max}$ şi $Q$, separate printr-un spaţiu. Pe linia a doua se se află $h_{max}$ numere $P_1$, $P_2$, $\dots$, $P_{h_{max}}$ separate prin câte un spaţiu reprezentând profiturile. Pe linia a treia se dau, separate prin câte un spaţiu, înălţimile $H_1$, $H_2$, $\dots$, $H_Q$ ale celor $Q$ panouri care se vor închiria

Date de ieșire

Fisierul de ieşire panou.out va conţine $Q$ linii, pe linia $k$, $1 \leq k \leq Q$, se va afla câte un număr reprezentând profitul maxim obţinut pentru al $k$-lea panou.

Restricții și precizări

• $1 \leq hmax \leq 100 \ 000$
• $1 \leq Q \leq 10 \ 000$
• $1 \leq P_i \leq 100 \ 000$
• $1 \leq H_i \leq 10 \ 000 \ 000$
• Pentru $70\%$ din punctaj $H_i \leq 100 \ 000$
• Pentru $10\%$ din punctaj $h_{max} \leq 1 \ 000$ şi $Q \leq 1 \ 000$

Exemplu

panou.in

3 2
1 3 5
6 8

panou.out

10
12

Explicație

Pentru $H = 6$ avem doua benzi de inaltime $3$ obtinand castigul maxim $2 \cdot 5 = 10$
Pentru $H = 8$ avem $4$ benzi de inaltime $2$ obtinand castigul maxim $4 \cdot 3 = 12$