fermier

Dorel și-a achiziționat o fermă cu $n$ plantații și o mașină de transport cu o capacitate $c$, pentru transportul de îngrășăminte la toate plantațiile. Îngrășămintele se află într-un depozit, în cantitate suficientă pentru scopul propus. Plantațiile și depozitul sunt dispuse sub forma unui cerc. Există drumuri doar între plantația $i$ și plantația $i+1$ ($1 \leq i \leq n-1$), precum și între depozit și plantația $1$ și depozit și plantația $n$, ca în figură. La o plantație $i$ se poate ajunge de la depozit trecând prin plantațiile $1, 2, \dots, i-1$ sau prin plantațiile $n, n-1, \dots, i+1$, alegerea făcându-se în funcție de traseul cel mai scurt. Se cunosc aceste distanțe, precum și cantitatea de îngrășăminte necesară pentru fiecare plantație. La fiecare încărcare, Dorel ia din depozit exact cantitatea $c$.

Dorel vrea să-și organizeze bine munca la fermă și să consume cât mai puțină benzină prin alegerea celor mai scurte trasee de parcurs. Plantațiile trebuie să fie aprovizionate obligatoriu în ordinea următoare: mai întâi plantația $1$, apoi plantația $2$, plantația $3$, $\dots$, plantația $n$. În plus, și-a propus să încarce o nouă cantitate de îngrășământ doar după ce a folosit toată cantitatea încărcată anterior. Transportarea îngrășămintelor pe plantații se face deci, începând cu plantația $1$. După ce se transportă toată cantitatea necesară pentru această plantație, se trece la plantația $2$, și tot așa în ordine la $3, 4$ etc. până se deservește ultima plantație. Dacă după ce s-au transportat îngrășămintele necesare pentru plantația $i$ în mașină au mai rămas încă îngrășăminte, acestea trebuie utilizate în continuare pentru alte plantații, alese în ordinea impusă (începând cu plantația $i+1$, apoi $i+2$ etc.), până se epuizează toată cantitatea transportată de mașină. Astfel, dacă de la plantația $i$ trebuie să ajungă la plantația $i+1$, va alege cel mai scurt traseu dintre traseul direct de la plantația $i$ la $i+1$ și traseul care trece prin plantațiile $i-1$, $i-2$, $\dots$, $1$, depozit, $n, n-1, \dots, i+1$. La final, mașina trebuie să se întoarcă la depozit, goală sau cu cantitatea rămasă după aprovizionarea cu îngrășăminte a plantației $n$.

Cerință

Ajutați-l pe Dorel să calculeze distanța parcursă pentru a transporta îngrășăminte la toate cele $n$ plantații, conform cerințelor.

Date de intrare

Fișierul de intrare fermier.in conține pe prima linie numerele naturale $n$ și $c$, separate printr-un spațiu. A doua linie conține numerele naturale $d_0, d_1, d_2, \dots, d_{n-1}, d_n$ separate două câte două prin câte un spațiu, unde $d_0$ este distanța dintre prima plantație și depozit, $d_i$ este distanța între plantația $i$ și plantația $i+1$, iar $d_n$ este distanța dintre plantația $n$ și depozit. Pe linia a treia se găsesc numerele naturale $q_1, q_2, \dots, q_{n-1}, q_n$ separate două câte două prin câte un spațiu, $q_i$ reprezentând cantitatea de îngrășăminte necesară pentru plantația $i$.

Date de ieșire

Fișierul de ieșire fermier.out va conține pe prima linie un număr natural conform cerinței.

Restricții și precizări

• $1 \leq n \leq 100$;
• $1 \leq n \leq 2$, pentru teste în valoare de $20$ de puncte;
• $1 \leq d_i, c, q_i \leq 1 \ 000$;
• Se acordă $10$ puncte din oficiu

Exemplu

fermier.in

3 6
1 10 2 3
13 2 7

fermier.out

22

Explicație

La plantația $1$ trebuie transportată o cantitate egală cu $13$, valoarea maximă pe care o poate transporta mașina fiind de $6$. La plantația $1$ se ajunge pe drumul cel mai scurt direct de la depozit. Astfel se va merge mai întâi cu cantitatea $6$, ne întoarcem la depozit, încărcam iar mașina, ducem $6$, ne întoarcem, încărcăm și lăsăm doar $1$ (atât mai este necesar). Pentru aceasta, s-a parcurs distanța de $1+1+1+1+1=5$. În mașină a mai rămas acum o cantitate egală cu $5$. Trebuie să mergem acum la plantația $2$ pe drumul cel mai scurt.

Pe drumul direct distanța este $10$, iar pe drumul invers care trece iar prin depozit este $6$ ($1+3+2$). Vom alege drumul cu distanța $6$. Lăsăm cantitatea $2$ (atât e necesar plantației $2$), ne mai rămân $3$ și pentru plantația $3$. De la plantația $2$ se ajunge direct la plantația $3$ pe o distanță egală cu $2$ sau invers, trecând
prin depozit pe o distanță de $14$ ($10+1+3$). Alegem drumul cu distanța $2$. Lăsăm îngrășămintele rămase și mai mergem iar la depozit, încărcăm și lăsăm $4$ la plantația $3$. Pentru aceasta mai parcurgem distanța $3+3$.

La final mașina trebuie să se întoarcă la depozit, deci încă un drum cu distanța $3$. În total: $5+6+2+6+3=22$