26609번 - 합의 곱의 절댓값의 최댓값

문제

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

"길이 $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}$을 넘지 않는다.

힌트