Background

[Midnight - 23:59]

At the kite festival, gyx made some good buddies (not Nishikino), got in touch with OI, and all of his passion was ignited!! To better take part in the work for the next kite festival, gyx is ready to start a one-year study plan.

Problem Description

gyx wants to use all his time to study (slack off on) OI (waste time)!!!

To use all his time reasonably to study OI, he starts planning his study schedule.

First, in gyx's eyes, each year has $n$ days. Because gyx really wants to study, he does not leave any time for entertainment (every day is fully used for studying OI or cultural courses). His rule for dividing days is: within each day, gyx's level of interest in OI is the same. However, since gyx may be unable to focus due to trivial life matters, on some days his interest in OI may be negative.

Then, gyx starts arranging the time for studying OI. He counts that there are $k$ types of OI knowledge he needs to learn. Because gyx pursues perfection, he believes that for each type of OI knowledge, the completeness of the knowledge system is necessary. If he stops in the middle of learning a part of OI knowledge, it will affect his learning results. Therefore, he will use several consecutive days to learn one part of knowledge. During this period, he cannot stop to study cultural courses, and he will not mix learning multiple types of knowledge.

Note that between learning different parts of OI knowledge, gyx can leave some time periods to study cultural courses. Also, gyx does not care about the order of learning different parts of OI knowledge, because his interest level is the same for each part of OI knowledge.

Now, gyx wants to know the sum of interest values over all days he spends studying OI. Since gyx has not learned advanced planning algorithms, he hands the planning of his study schedule to you. You may choose any positive integer $i \le n$ so that he starts from day $i$ and studies for $n$ days (he does not have to study OI at the beginning). However, within this year, he must finish learning all the knowledge on the list. gyx believes you can surely give a plan with the maximum possible sum of interest values.

Input Format

Two positive integers $n, k$, representing that in gyx's eyes a year has $n$ days, and there are $k$ types of knowledge he needs to learn.

The next line contains $n$ integers. The $i$-th number $a_i$ represents gyx's interest level in OI on day $i$.

Output Format

Output one integer, representing the maximum possible sum of interest values over all days he studies OI.

6 2
2 -4 3 -1 2 3

10

Hint

Sample Explanation

Starting to study from the $3$-rd time period, the interest sequence for that year of studying OI becomes:

• $[3,-1,2,3,2,-4]$.

The time periods used to learn the two types of knowledge are the $1$-st, and the $3, 4, 5$-th elements of the new sequence, so $ans = 3 + (2 + 3 + 2) = 10$.

Constraints

• For $10\%$ of the testdata, $k = 1$ holds.
• For another $30\%$ of the testdata, $k = 2$ holds.
• For $100\%$ of the testdata: $1 \le k \le 50$, $k \le n \le 10^5$, $|a_i| \le 10^4$.

Translated by ChatGPT 5