== include(page="template/taskheader" task_id="easyvect") ==

Tanarul nobil Naelav doreste sa cucereasca inima prea frumoasei si priceputei Niros, fata regelui Arpsod, stapanul regatului Valores. El se gandeste sa o impresioneze facand niste armuri cu totul si cu totul din haur pentru dragonii ei. Tatal sau refuza insa sa cheltuiasca atat de multi bani pentru o pasiune adolescentina asa ca Naelav paraseste regatul amenintand oamenii cu catapulta sa care arunca blaturi tari ca piatra.
Regatul Valores este alcatuit din N orase dispuse in linie. Astfel din orasul $i$ se poate ajunge in orasele $i+1$ si $i-1$, exceptie facand orasele $1$ si $N$. Urmeaza o lunga serie de $x$ episoade. In fiecare episod, Naelav asediaza un anume oras $i$, sustrage din visteria acestuia $v[~i~]$ monezi de haur si porneste catre unul din orasele adiacente. El poate ataca un oras de mai multe ori pentru aceeasi suma, dar nu in episoade consecutive.
Pentru a putea da cat mai multe spoilere prietenilor tai, te gandesti sa aflii care ar fi valoarea maxima pe care ar putea-o colecta Naelav in $x$ episoade, in $Q$ astfel de scenarii.

Tanarul nobil Naelav doreste sa cucereasca inima prea frumoasei si priceputei Adnana, fata regelui Arpsod, stapanul regatului Valores. El se gandeste sa o impresioneze facand niste armuri cu totul si cu totul din haur pentru dragonii ei. Tatal sau refuza insa sa cheltuiasca atat de multi bani pentru o pasiune adolescentina asa ca Naelav paraseste regatul amenintand oamenii cu catapulta sa, care arunca blaturi tari ca piatra.
Regatul Valores este alcatuit din N orase dispuse in linie. Astfel din orasul $i$ se poate ajunge in orasele $i+1$ si $i-1$, exceptie facand orasele $1$ si $N$. Urmeaza o lunga serie de $x$ episoade. In fiecare episod, Naelav asediaza un anume oras $i$, sustrage din visteria acestuia $v[~i~]$ monezi de haur si porneste catre unul din orasele adiacente. El poate ataca un oras de mai multe ori pentru aceeasi suma, dar nu in episoade consecutive. Stim ca primul oras ce a fost deja asediat este chiar orasul sau natal, orasul cu numarul $1$.
Pentru a putea da cat mai multe spoilere prietenilor tai, te gandesti sa aflii care ar fi valoarea maxima pe care ar putea-o colecta Naelav in urmatoarele $x$ episoade, in $Q$ astfel de scenarii.

h2. Date de intrare

Fişierul de intrare $easyvect.in$ contine pe prima linie numarul $T$, numarul de teste. Fiecare test va contine numerele $N$ si $Q$ numarul de orase, respectiv numarul de intrebari si un sir de $N$ numere pe linia urmatoare, reprezentand cantitatea de monezi $v[~i~]$ din fiecare oras. Pe urmatoarele $Q$ linii sunt descrise numerele $x$, reprezentand numarul de episoade pe care le-ar putea avea serialul.

Fişierul de intrare $easyvect.in$ contine pe prima linie numarul $T$, numarul de teste. Fiecare test va contine numerele $N$ si $Q$ numarul de orase, respectiv numarul de intrebari si un sir de $N$ numere pe linia urmatoare, reprezentand cantitatea de monezi care se pot obtine $v[~i~]$ din fiecare oras intr-un episod. Pe urmatoarele $Q$ linii sunt descrise numerele $x$, reprezentand numarul de episoade pe care le-ar putea avea serialul.

h2. Date de ieşire

* $2 ≤ N ≤ 10^5$
* $1 ≤ Q ≤ 10^5$
* $1 ≤ v[~i~] ≤ 10^5$

* $1 ≤ x ≤ 10^9$, pentru fiecare query din cele $q$

* $1 ≤ x ≤ 10^9$, pentru fiecare query din cele $Q$

* **Atentie!** Rezultatul poate depasi numere pe 32 de biti.

* Naelav este mai mult taran decat nobil
* Suparat ca nu o poate cuceri pe Adnana, Naelav se inchide in camera sa si se joaca cu dragonul sau micut.

h2. Exemplu