log

Fie expresia: $log_{a_1}b_1 \cdot log_{a_2}b_2 \cdot … \cdot log_{a_n}b_n$

Un calculator trebuie să evalueze această expresie aducând-o la forma unui singur număr real. Pentru aceasta, el poate face următoarele calcule:

• Produs = produsul a doua numere reale în $t_1$ unităţi de timp;
• Reducere = înlocuirea expresiei $log_ab \cdot log_bc$ cu $log_ac$ în $t_2$ unităţi de timp;
• Calcul = calculul unui logaritm, rezultatul fiind un număr real; pentru a calcula $log_ab$ îi sunt necesare $t_3 \cdot (a-b)^2$ unităţi de timp.

Cerinţă

Să se determine timpul minim pentru a calcula o expresie dată.

Date de intrare

Fişierul log.in conţine:

• pe prima linie o valoare numerică naturală n cu semnificaţia din enunţ;
• pe a doua linie trei valori numerice naturale $t_1 t_2 t_3$ separate prin câte un spaţiu, cu semnificaţia din enunţ;
• pe fiecare din următoarele n linii câte două valori numerice naturale $a_i b_i$ cu semnificaţiile din enunţ.

Date de ieşire

Fişierul log.out va contine o singură valoare reprezentând numărul de unităţi de timp necesare evaluării expresiei.

Restricţii şi precizări

• Pentru 70% din teste 0 < n ≤ 500; pentru celelalte 30% din teste n ≤ 10000;
• $1 < a_i,b_i < 100$
• $1 ≤ t_1,t_2,t_3 ≤ 100$
• Factorii expresiei iniţiale sau ai oricăreia dintre expresiile rezultate pe parcursul evaluării NU pot fi comutaţi între ei.

Exemplu

log.in

3		
2 1 3
2 3
3 4
4 5

log.out

13

Explicaţii

Se calculează fiecare din cei trei logaritmi, rezultă trei numere, fiecare calcul necesită 3 unităţi de timp; se înmulţesc primele două numere în 2 unităţi de timp, apoi rezultatul se înmulţeşte cu al treilea număr tot în 2 unităţi; în total: 3+3+3+2+2=13 unităţi.

log.in

4		
2 1 2
2 2
3 4
4 4
4 5

log.out

9

Explicaţii

Primul logaritm se calculează în 0 unităţi; al doilea şi al treilea se reduc la un logaritm în 1 unitate iar acest logaritm se calculează în 2 unităţi; al patrulea se calculează în 2 unităţi; au rezultat trei numere, care pot fi aduse la unul singur prin două înmulţiri, fiind necesare 1+2+2+2+2=9 unităţi de timp.