Tarzan

Time limit: 0.6s Memory limit: 256MB Input: Output:

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 NN copaci pentru jungla lui Tarzan, numerotați de la 11 la NN, fiecare fiind etichetat prin 2 valori, AA și BB. La crearea unei liane între 2 copaci ii și jj, Tarzan trebuie să plătească un cost egal cu AiAj+Bi+BjA_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 NN şi cele două șiruri AA și BB, aflați costul minim de întregire a junglei.

Date de intrare

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

Date de ieșire

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

Restricții și precizări

  • 1N100 0001 \leq N \leq 100 \ 000;
  • 1Ai1061 \leq A_i \leq 10^6, pentru orice 1iN1 \leq i \leq N;
  • 1Bi10121 \leq B_i \leq 10^{12}, pentru orice 1iN1 \leq i \leq N;
# Punctaj Restricții
1 7 N1 000N \leq 1 \ 000
2 14 N10 000N \leq 10 \ 000
3 18 În șirul AA există maxim 100100 de numere diferite.
4 14 Testele sunt generate aleator.
5 47 Fără restricții suplimentare.

Exemplu

stdin

5
7 9 6 7 5
14 13 15 9 100

stdout

363

Explicație

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

Log in or sign up to be able to send submissions!