Triplets
Есенен Турнир по Информатика 2009
Time Limit: 0.1s, Memory Limit: 64MiB
Ели реши най-накрая да почне да работи! И тъй като не всяка работа е за нея, тя се захвана с това да прави приложения за небезизвестния сайт Phasebook. Тя има идеята да имплементира следната игра:

Всеки играч започва със сума нула и маса с N пула със стойности числата A1, A2, ..., AN. Той има право да:
  1. Вземе произволен пул, да прибави към сумата си стойността му и да го махне от масата.
  2. Вземе произволни два пула, да прибави произведението на стойностите им към сумата си и да ги премахне от масата.
  3. Вземе произволни три пула, да прибави произведението на стойностите им към сумата си и да ги премахне от масата.
Играта приключва когато не останат пулове и резултатът на играча е неговата сума. Играчът с най-голяма сума печели.

Елеонора е решила да именува играта "CreateTriples" и е много горда от оригиналното си творение (което няма нищо общо с "CreatePairs", която е същата игра без третото правило). Някои играчи се справят учудващо добре (предимно информатиците), докато други не чак толкова. А как ще се справите Вие?
Вход
На първия ред на стандартния вход ще бъде зададен броят пулове N, а на втория ще има N цели числа A1, A2, ..., AN – стойностите на всеки пул.
Изход
На единствен ред на стандартния изход изведете максималната сума, която можете да постигнете при оптимална игра.
Ограничения
  • 1 ≤ N ≤ 1,000
  • -30,000 ≤ Ai ≤ 30,000
Примерен Вход Примерен Изход
3 -16 0 42 42
7 0 2 -1 2 7 -3 -4 88
В първия тест единственото решение е да вземем 42 + (-16 * 0) и да получим 42.
Едно от решенията на втория тест е да се вземат (-4, -3, 7), (-1, 0), (2), (2), даващо 84 + 0 + 2 + 2 = 88.
Мрън!