这题基本上就是 AcWing 163. 生日礼物 的双倍经验，自然可以用 wqs 二分来完成。但是那个题是至多选择 $k$ 个非空子段，所以答案偏移的下界可以从 $0$ 开始，一旦最优答案下界是 $0$ ，意味着可以不取满 $k$ 个。但是本题强制要求 $k$ 个子段（也就是可能哪怕会使得答案变小也要捏着鼻子选负数），所以 wqs 二分的下界需要调整为 $-\infty$ 。

const int N = 1000010;
// pre = max_{1\le j\le i} f_j 
int n, k;
i64 a[N], s[N];
// <max dp, min seg>
struct dp_info
{
    i64 dp;
    int seg;
    dp_info(i64 d = 0, int s = 0) : dp(d), seg(s) {}
    bool operator==(const dp_info& o) const { return (dp == o.dp) && (seg == o.seg); }
    bool operator>(const dp_info& o) const { return (dp > o.dp) || ((dp == o.dp) && (seg < o.seg)); }
    bool operator<(const dp_info& o) const { return !(((*this) == o) || ((*this) > o)); }
};
dp_info pre[N], f[N];
int mx_ptr;
dp_info solve(i64 v)
{
    pre[0] = f[0] = dp_info(0, 0), mx_ptr = 0;
    for (int i = 1; i <= n; ++i)
    {
        // f[i] = pre[j] + (s[i] - s[j] - v) (0\le j < i)
        f[i] = dp_info(pre[mx_ptr].dp + s[i] - s[mx_ptr] - v, pre[mx_ptr].seg + 1);
        pre[i] = std::max(pre[i - 1], f[i]);
        mx_ptr = ((pre[i].dp - s[i]) > (pre[mx_ptr].dp - s[mx_ptr])) ? i : mx_ptr;
    }
    dp_info ans = dp_info(0, 0);
    for (int i = 1; i <= n; ++i)
        ans = std::max(ans, f[i]);
    return ans;
}
int main()
{
    while (scanf("%d%d", &k, &n) != EOF)
    {
        for (int i = 1; i <= n; ++i)
            a[i] = rd(), s[i] = s[i - 1] + a[i];
        i64 lo = -2000000000, hi = 2000000000, mi = 0;
        while (lo < hi)
        {
            mi = (lo + hi) >> 1;
            (solve(mi).seg > k) ? (lo = mi + 1) : (hi = mi);
        }
        wr(solve(lo).dp + lo * k), putchar('\n');
    }
}