Casino
Дизайн и Анализ на Алгоритми, 2011
Time Limit: 0.1s, Memory Limit: 64MiB
След като взе първата заплата от стажа си, Ели реши да инвестира парите в нещо сигурно и доходоносно – а именно, хазарт. Тя беше чула, че в едно от новите казина има интересна игра със следните правила:

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