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

Comisia AGM mai avea nevoie de o problema usoara. Stiind ca Elf nu a fost in stare sa treaca de OJI, se gandesc sa-i dea lui responsabilitatea. El stie cel mai bine vectori din toata informatica, asa ca se gandeste sa dea o problema usoara cu ei.
 
Aveti un vector $a$ cu $n$ elemente $pozitive$ si $q$ query-uri. Un query este dat de un numar $x$. Initial porniti din pozitia 1 a vectorului. Trebuie sa va plimbati $x$ unitati de timp. Din pozitia 1, puteti ajunge doar in pozitia 2. Din pozitia $n$, puteti ajunge doar in pozitia $n - 1$. Altfel, din pozitia $i$ se poate ajunge atat in pozitia $i - 1$, cat si in pozitia $i + 1$. Cand Elf este intr-o casuta, el aduna in sacul de valoare numarul scris acolo. Care este suma maxima pe care-o poate obtine dupa $x$ timp? Si numarul aflat pe pozitia 1 intra in tolba de valoare!

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.

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 cu semnificatia din enunt si un sir de N numere pe linia urmatoare. Pe urmatoarele Q linii sunt descrise numerele x, corespunzatoare query-urilor.

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.

h2. Date de ieşire

În fişierul de ieşire $easyvect.out$ se vor afisa q linii, cate una pentru fiecare query.

În fişierul de iesire $easyvect.out$ se vor afisa $T*Q$ linii, cate una pentru fiecare query.
 

h2. Restricţii
* $1 ≤ T ≤ 10$
* $2 ≤ N ≤ 10^5$
* $1 ≤ Q ≤ 10^5$

* $1 ≤ a[~i~] ≤ 10^5$

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

* $1 ≤ x ≤ 10^9$, pentru fiecare query din cele $q$
* **Atentie!** Rezultatul poate depasi numere pe 32 de biti.