합의 곱의 절댓값의 최댓값

수학에는 정말 아름다운 기호가 많다. 수학나라의 수학왕은 특히 합, 곱, 절댓값을 좋아한다. 수학왕은 당신에게 다음의 문제를 냈다.

"길이 $N$인 정수로 이루어진 수열 $A$가 주어진다. 그 뒤, 서로 겹치지 않게 $K$개 이하의 구간을 잡는다. 이때, 각 구간의 길이는 $1$ 이상이어야 한다.

구간의 개수를 $X(\ge 1)$개 라고 할 때, 각 구간의 원소의 합을 $S\_i (i = 1, 2, \cdots, X)$라 하자. 이때 $\left\vert S\_1 S\_2 \cdots S\_X \right\vert$의 최댓값은 무엇인가?"

수학왕에게 인정받기 위해 문제를 해결하자!

첫 번째 줄에 $N, K$가 주어진다.

이후 $N$줄에 걸쳐 $i + 1$번째 줄에 $A\_i$가 주어진다.

첫 번째 줄에 $K$개 이하의 구간을 잡았을 때의 최댓값을 출력한다.

• $1$ $\leq$ $N$ $\leq$ $100000$
• $1$ $\leq$ $K$ $\leq$ $6$
• $-10^9$ $\leq$ $A\_i$ $\leq$ $10^9$
• 답은 $10^{18}$을 넘지 않는다.