Cladiri

Ciprian stătea pe treapta din fața școlii, cu caietul deschis şi cu pixul pregătit să noteze idei. Zilele trecute intraseră într-o competiție de informatică regională, iar tema lui de suflet era optimizarea: găsirea celei mai bune soluții pentru probleme aparent simple, dar cu mii de erori ascunse.

Într-o seară, la laboratorul de informatică, profesorul de informatică, Marian, a desenat pe tablă două șiruri de numere: înălțimile clădirilor de pe bulevard, $H_{1}, H_{2}, \ldots, H_{n}$, și profiturile, $W_{1}, W_{2}, \ldots, W_{n}$. „Imaginați-vă că vreți să alegeți un segment continuu de clădiri pe care să îl închiriați pentru un festival stradal.” explică el. „Însă contractul cere ca toate clădirile să aibă cel puțin înălțimea $T$, iar profitul vostru să fie cât mai mare posibil.”

Ciprian a început imediat să-și imagineze cartierul: clădiri vechi cu fațade colorate, unele zgârie-nori eleganți, altele case modeste cu un etaj. Fiecare clădire era caracterizată de două valori: înălțimea și profitul zilnic. Pentru fiecare prag $T$ dat de organizatorii festivalului, el trebuia să răspundă rapid care e suma maximă a profiturilor pe care o putea obține selectând un interval de clădiri cu toate înălțimile mai mari sau egale cu $T$.

Cerință

Fiind date $N$, $Q$, $H_{i}$ și $W_{i}$ pentru $1 \leq i \leq N$, răspunde la $Q$ întrebări de următorul fel: fie pragul $T$, găsește cea mai mare sumă a costurilor unui segment continuu de clădiri $\left[L, R\right]$, astfel încât toate clădirile din acel segment să aibă înălțimea cel puțin $T$.

Date de intrare

Fișierul de intrare cladiri.in conține:

• pe prima linie două numere naturale, $N$ și $Q$, cu semnificația din enunț;
• pe următoarea linie $N$ numere naturale, al $i$-lea număr corespunde lui $H_{i}$;
• pe următoarea linie $N$ numere naturale, al $i$-lea număr corespunde lui $W_{i}$;
• pe următoarele $Q$ linii, $Q$ numere naturale, câte unul pe fiecare linie, care corespunde $T$-ului din cerință.

Date de ieșire

Pentru fiecare $1 \leq i \leq Q$, afișează în cladiri.out pe câte o linie un număr: costul maxim al unui segment de clădiri $\left[L, R\right]$, cu toate înălțimile mai mari sau egale cu $T_{i}$, sau $0$ dacă nu există niciun segment valid.

Restricții și precizări

• $1 \leq N, Q \leq 2 \cdot 10^{5}$;
• $1 \leq H_{i} \leq 10^{9}, 1 \leq i \leq N$;
• $1 \leq W_{i} \leq 10^{6}, 1 \leq i \leq N$;
• $1 \leq T_{i} \leq 10^{9}, 1 \leq i \leq N$;

Exemplu

cladiri.in

8 5
2 1 4 3 5 2 6 4
3 2 1 4 5 1 2 3
1
3
4
5
7	

cladiri.out

21
10
5
5
0

Explicație

Pentru prima întrebare, $T = 1$, orice clădire convine. Costul maxim este $3 + 2 + 1 + 4 + 5 + 1 + 2 + 3 = 21$.
Pentru a doua întrebare, $T = 3$, pozițiile eligibile sunt $\left\{1, 3, 4, 5, 7, 8\right\}$. Segmente valide: $\left[1,1\right]$, cu suma 3, $\left[3,5\right]$, cu suma 10, $\left[7, 8\right]$, cu suma 5. Suma maximă este 10, pe segmentul $\left[3, 5\right]$.
Pentru a patra întrebare, $T = 5$, pozițiile eligibile sunt $\left\{5, 7\right\}$. Segmente valide: $\left[5,5\right]$, cu suma 5, $\left[7,7\right]$, cu suma 2. Suma maximă este 5, pe segmentul $\left[5, 5\right]$.
Pentru a cincea întrebare, $T = 7$, nu există clădiri care să aibe înălțimea mai mare sau egală cu 7. Vom afișa 0.