Impartire

Cerință

Se dau $N$, $A$, $B$, $C$ și un vector $V$ de mărime $N$.

Se aleg $2$ indici, $1 <= i < j < N$ și se face împărțirea șirului $V$ în subsecvențele $[1...i], [i+1...j], [j+1...N]$, să le numim $S_1$, $S_2$ și $S_3$.

Care este valoarea maximă care se poate obține pentru $A * G_1 + B * G_2 + C * G_3$, unde $G_1$, $G_2$ și $G_3$ sunt cel mai mare divizor comun al elementelor din cele $3$ secvențe.

Date de intrare

Pe prima linie se găsesc numerele $N$, $A$, $B$ și $C$. Pe următoarea linie se găsește șirul $V$.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, valoarea maximă cerută.

Restricții și precizări

• $3 \leq N \leq 10^5$;
• $1 \leq A, B, C, V_i \leq 10^9$
• Pentru 20 de puncte $1 \leq N \leq 200$
• Pentru alte 40 de puncte $1 \leq N \leq 1000$

Exemplul 1

stdin

6 1 1 1
6 6 9 9 3 7

stdout

16

Explicație

Se alege $i=2$, $j=5$