expresie

Expresie

== include(page="template/taskheader" task_id="expresie") ==

Costel are de rezolvat o temă grea la matematică: având la dispoziţie $N$ numere naturale nenule trebuie să aşeze între acestea 2 operaţii de înmulţire şi $N-3$ operaţii de adunare, astfel încât rezultatul calculelor să fie cel mai mare posibil. Nu este permisă modificarea ordinii numerelor date.
De exemplu, dacă $N=5$ şi numerele sunt $4$, $7$, $1$, $5$, $3$,  operaţiile pot fi aşezate $4 + 7 * 1 + 5 * 3, 4 * 7 *1 + 5 + 3$ etc.

Costel are de rezolvat o temă grea la matematică: având la dispoziţie $N$ numere naturale nenule trebuie să aşeze între acestea 2 operaţii de înmulţire şi $N - 3$ operaţii de adunare, astfel încât rezultatul calculelor să fie cel mai mare posibil. Nu este permisă modificarea ordinii numerelor date. De exemplu, dacă $N = 5$ şi numerele sunt $4$, $7$, $1$, $5$, $3$,  operaţiile pot fi aşezate $4 + 7 * 1 + 5 * 3, 4 * 7 * 1 + 5 + 3$ etc.
 
h2. Cerinţă
 
Scrieţi un program care să aşeze două operaţii de înmulţire şi $N - 3$ operaţii de adunare între cele $N$ valori date astfel încât valoarea expresiei obţinute să fie maximă.

h2. Date de intrare

Fişierul de intrare $expresie.in$ ...

Fişierul de intrare $expresie.in$ va contine pe prima linie un număr natural $N$, reprezentând numărul elementelor date. Pe următoarele linii se află cele $N$ numere naturale date, fiecare pe câte o linie.

h2. Date de ieşire

În fişierul de ieşire $expresie.out$ ...

Fişierul de ieşire $expresie.out$ va conţine, pe prima linie, valoarea maximă obţinută prin evaluarea expresiei

h2. Restricţii

* $... ≤ ... ≤ ...$

* $4 ≤ N ≤ 1.000$
* Numerele date sunt numere naturale între $1$ şi $10.000$

h2. Exemplu
table(example). |_. expresie.in |_. expresie.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5
4
7
1
5
3
| 44

|
h3. Explicaţie

...

Valoarea maximă se obţine prin aşezarea operaţiilor sub forma: $4 * 7 + 1 + 5 * 3$
 

== include(page="template/taskfooter" task_id="expresie") ==

4638