optim

Gigel primea de la mama lui, ca temă, o foaie pe care era scris un șir de $N$ numere întregi. Singurul calcul pe care știa să îl facă
până acum era suma tuturor numerelor. Pentru aceasta el plasa $N-1$ semne de adunare, $+$, între numerele aflate pe poziții consecutive în șir și calcula astfel suma acestor numere. Între timp a crescut și a învățat și operația de înmulțire pentru care folosește semnul $\cdot$. Din șirul celor $N-1$ semne de adunare, îi trece prin minte să înlocuiască $K$ semne $+$ cu $K$ semne $\cdot$.

Își dă seama că tema se complică, deoarece înmulțirile trebuie efectuate înaintea adunărilor, dar nu se dă bătut și duce calculul până la capăt.

Cerinţă

Scrieţi un program care să determine valoarea minimă pe care o poate obţine şi valoarea maximă pe care o poate obţine după înlocuirea menţionată.

Date de intrare

Fişierul de intrare optim.in conţine pe prima linie numerele naturale $N$ şi $K$, separate printr-un spaţiu, reprezentând numărul de numere întregi din şir, respectiv numărul de operaţii de înmulţire ce vor fi efectuate. Pe cea de a doua linie se află $N$ numere întregi separate prin câte un spaţiu, $x_1, x_2, \dots, x_N$, reprezentând numerele din şir.

Date de ieșire

Fişierul de ieşire optim.out va conţine pe o singură linie, separate printr-un spaţiu, în ordine crescătoare, cele două valori cerute.

Restricții și precizări

• $2 \leq N \leq 30$;
• $0 \leq K \leq 9; K \lt N$
• $-8 \leq x_i \leq 8, 1 \leq i \leq N$
• Dacă fişierul de ieşire conţine exact două numere, dar doar unul este corect, se obţine $40\%$ din punctajul acordat testului respectiv.

Exemplu

optim.in

6 3
2
0
3
-1
7
-4

optim.out

-31 86

Explicație

$2 \cdot 0 + 3 \cdot (-1) + 7 \cdot (-4) = -31$
$2 + 0 + 3 \cdot (-1) \cdot 7 \cdot (-4) = 86$