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 *. Din şirul celor N-1 semne de adunare, îi trece prin minte să înlocuiască K semne + cu K semne *.
Îş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, x1 x2 ... xN, 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
• 2 ≤ N ≤ 30
• 0 ≤ K ≤ 9; K < N
• -8 ≤ xi ≤ 8, 1 ≤ i ≤ N