题目描述 给定一个长度为 $n$ 的数列 $A = a 1, a 2, \ldots, a i, \ldots, a n$，其中 $1 \leq i \leq n \leq 2000000$，$-50000 \leq a i \leq 50000$。 当给定两个整数 $x$ 和 $y$（$1 \leq x \leq y \leq n$），$A[x:y]$ 表示数列 $A$ 从下标 $x$ 到下标 $y$ 的子段；同时，$sum(x, y)$ 表示子段 $A[x:y]$ 中所有元素的和（即 $sum(x, y) = \sum {i=x}^{y} a i$）。 给定两个关于数列 $A$ 的子段：$A[x 1:y 1]$ 和 $A[x 2:y 2]$，当 $x 1 \leq y 1 < x 2 \leq y 2$ 或者 $x 2 \leq y 2 < x 1 \leq y 1$ 时，则 $A[x 1:y 1]$ 和 $A[x 2:y 2]$ 这两个子段是不相交的。 现在给定一个正整数 $m$，请找到数列 $A$ 的 $m$ 个互相不相交的子段（$A[x 1:y 1]$, $A[x 2:y 2]$, $\ldots$, $A[x k:y k]$, $\ldots$, $A[x m:y m]$），使得 $\sum {k=1}^{m} sum(x k, y k)$ 的值最大。 输入格式 输入包含 $2$ 行： 第 $1$ 行为 $2$ 个整数 $m$ 和 $n$（$m$ 和 $n$ 的含义如上述所示）； 第 $2$ 行为 $n$ 个整数，$a 1, a 2, \ldots, a n$，用来表示数列 $A$。 输出格式 输出仅 $1$ 行：$\sum {k=1}^{m} sum(x k, y k)$ 的最大值。 输入样例 3 8 -1 -2 10 -3 7 -4 5 -9 3 输出样例 22