Abonamente

Gigel vrea să își cumpere abonamente la $N$ companii. Fiecare companie vinde trei tipuri de abonamente (Gigel nu poate să cumpere mai mult de un abonament de la o singură companie). Gigel îi atribuie fiecărui abonament un scor bazat pe cât de util este acesta în viața sa de zi cu zi.

Abonamentul starter al companiei $i$ costă $0$ monede și are scorul $a_i$, abonamentul standard costă $1$ monede și are scorul $b_i$, iar abonamentul premium costă $2$ monede și are scorul $c_i$.

Cerință

Deoarece Gigel se duce la cazino în aceasta seara, el nu știe câte monede va mai avea pentru cumpărarea abonamentelor, de aceea el vă pune $Q$ întrebări în care vă spune câte monede mai are dupa seara de cazino. Ajutați-l pe Gigel să găsească suma maximă a scorurilor abonamentelor pe care le poate cumpăra de la cele $N$ companii, pentru fiecare scenariu cerut.

Date de intrare

Pe prima linie se găsesc două numere întregi, $N$ si $Q$.
Pe a doua linie se găsesc $N$ numere întregi reprezentând șirul $a$.
Pe a treia linie se găsesc $N$ numere întregi reprezentând șirul $b$.
Pe a patra linie se găsesc $N$ numere întregi reprezentând șirul $c$.
Pe următoarea linie se află $Q$ numere întregi $K_i$ reprezentând numărul de monede pe care Gigel dorește să le cheltuiască pe abonamente.

Date de ieșire

Pe prima linie se vor afla $Q$ numere, al $i$-lea dintre ele reprezentând răspunsul la a $i$-a întrebare.

Restricții și precizări

$\textcolor{red}{Atenție!}$ Din cauza numărului mare de date de intrare, respectiv ieșire, vă recomandăm să adăugați următoarele linii de cod la începutul funcției main().

ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

• $1 \leq N \leq 300 \ 000$
• $1 \leq Q \leq 2 \cdot N$
• $1 \leq K \leq 2 \cdot N$
• $0 \leq a_i \leq b_i \leq c_i \leq 10^9$
• Gigel cumpără exact un abonament de la fiecare companie

Exemplu

stdin

4 3
2 2 1 0
8 3 2 1
9 7 3 12
1 3 6

stdout

11 
23 
29

Explicație

Vom explica răspunsul doar la a doua întrebare $(K = 3)$:

Gigel va cumpăra abonamentul standard de la prima companie, abonamentul starter de la a $2$-a si a $3$-a companie și abonamentul premium de la a $4$-a companie. Suma scorurilor acestor abonamente este $8 + 2 + 1 + 12 = 23$.