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 rândul 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 ≤ h ≤ hmax. Î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], …, P[hmax], Gigel își dorește să afle pentru o listă de panouri H[1], H[2], …, H[Q] care vor fi profiturile maxime asociate.

Date de intrare

Fișierul de intrare panou.in conține pe prima linie hmax şi Q, separate printr-un spațiu. Pe linia a doua se se află hmax numere P[1], P[2], …, P[hmax] 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], …, H[Q] ale celor Q panouri care se vor închiria.

Date de ieșire

Fișierul de ieșire panou.out va conține Q linii, pe linia k, 1 ≤ k ≤ 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 ≤ hmax ≤ 100 000
• 1 ≤ Q ≤ 10 000
• 1 ≤ P[i] ≤ 100 000
• 1 ≤ H[i] ≤ 10 000 000
• Pentru 70% din punctaj H[i] ≤ 100 000
• Pentru 10% din punctaj hmax ≤ 1000 şi Q ≤ 1000

Exemplu:

panou.in

3 2
1 3 5 
6 8

panou.out

10
12

Explicație

Pentru H = 6 avem doua benzi de înălțime 3 obținând câștigul maxim 2*5=10. Pentru H = 8 avem 4 benzi de înălțime 2 obținând câștigul maxim 4*3=12.