Expression
Турнир за Купата на Декана, 2015
Time Limit: 0.1s, Memory Limit: 64MiB
Ели разполага с N цели числа, M знака минус и P знака плюс. Знае се, че M + P = N – 1. Mомичето иска да разположи числата в някакъв ред и да сложи по един от знаците между всяка двойка числа, така че полученият израз да дава възможно най-голямо число. Помогнете на момичето, като изчислите колко ще е това число.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N, M, и P – съответно броя числа, броя минуси, и броя плюсове. На следващия ред ще бъдат зададени N цели числа A1, A2, ..., AN.
Изход
На стандартния изход изведете едно цяло число – максималната сума, която може да се получи при създаване на израз, съдържащ всички числа и всички знаци.
Ограничения
  • 1 ≤ N ≤ 100
  • -1000 ≤ Ai ≤ 1000
  • 0 ≤ M, P < N
  • М + P = N – 1
Примерен Вход Примерен Изход
5 3 1 -6 11 -13 17 5 42
1 0 0 666 666
8 6 1 766 503 -393 819 446 544 777 -116 -154
Най-доброто, което можем да направим в първия пример, е: 11 - (-6) - (-13) + 17 - 5 = 42.
Мрън!