Mirror Cupa SEPI Seniori | Tarzan

Tarzan, eroul nostru preferat din jungla africană, a simțit nevoia unei noi încercări: Australia. Ajuns pe continentul cangurilor, acesta este cuprins de neliniște la vederea dezastrului natural provocat de incendii. Jungla nu mai are liane! Deznădăjduit, acesta este pus în contact, de către Jane, cu Asociația Copacilor Mistici Înțelepți ai Australiei, care îi oferă posibilitatea să reconstruiască prețioasa sa junglă, dar, evident, în schimbul unui preț.

În registrele Asociației sunt consemnați $N$ copaci pentru jungla lui Tarzan, numerotați de la $1$ la $N$, fiecare fiind etichetat prin 2 valori, $A$ și $B$. La crearea unei liane între 2 copaci $i$ și $j$, Tarzan trebuie să plătească un cost egal cu $A_i \cdot A_j + B_i + B_j$.
Tarzan, fiind mai puțin priceput în a face calcule, are nevoie de ajutorul vostru pentru a-și duce la final planurile! Știind oarecum că banii au valoare în societatea zilelor noastre (a încercat Jane să-i explice în timp ce el și o gorilă se spălau reciproc), el vă roagă să-i prezentați schema de cost minim a agățării lianelor care să îi permită să se balanseze de la orice copac la oricare altul (posibil folosind copaci intermediari)!

Cerință

Date fiind $N$ şi cele două șiruri $A$ și $B$, aflați costul minim de întregire a junglei.

Date de intrare

Pe prima linie se află numărul natural $N$ având semnificaţia din enunţ. Pe următoarele 2 linii se află elementele șirului $A$, respectiv ale șirului $B$.

Date de ieșire

Pe prima linie se află costul minim al reasambării junglei lui Tarzan.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$;
• $1 \leq A_i \leq 10^6$, pentru orice $1 \leq i \leq N$;
• $1 \leq B_i \leq 10^{12}$, pentru orice $1 \leq i \leq N$;

Exemplu

stdin

5
7 9 6 7 5
14 13 15 9 100

stdout

363

Explicație

Putem construi lianele: $(1, 3)$, $(2, 3)$, $(3, 4)$, $(4, 5)$