Maximum Absolute Value of the Product of Interval Sums

Time limit1sMemory limit256 MB

Summary

Given an integer array and at most K non-overlapping intervals, find the maximum absolute value of the product of the interval sums.

Level: Hard8 of 10
Topics: Dynamic programming, Prefix sum, Math
Solved: No attempts yet

Problem

Mathematics has many beautiful symbols. The Math King of Mathland especially likes sums, products, and absolute values. The Math King gave you the following problem.

You are given an integer sequence $A$ of length $N$ . Then choose at most $K$ intervals that do not overlap each other. Each interval must have length at least $1$ .

Let the number of intervals be $X(\ge 1)$ , and let $S_i$ ( $i = 1, 2, \cdots, X$ ) be the sum of the elements in the $i$ -th interval. What is the maximum value of $\left\vert S_1 S_2 \cdots S_X \right\vert$ ?

Solve the problem to earn the Math King's respect!

Input

The first line contains $N, K$ .

The next $N$ lines contain $A_i$ on the line $i + 1$ .

Output

Print the maximum value when at most $K$ intervals are chosen, on the first line.

Constraints

$1 \leq N \leq 100000$
$1 \leq K \leq 6$
$-10^9 \leq A_i \leq 10^9$
The answer does not exceed $10^{18}$ .

Examples2

Example 1
Input
```
6 2
6
-5
5
5
5
5
```
Expected output
```
120
```
Example 2
Input
```
5 2
5
5
5
5
5
```
Expected output
```
150
```