题目描述 给定一个长度为 $n$ 的数列 $A = a 1, a 2, \cdots, a i, \cdots, 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$ 的子段，同时 $\text{sum}(x, y)$ 表示子段 $A[x : y]$ 中所有元素的和（即 $\text{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$ 时，这两个子段是不相交的。 现在给定一个正整数 $m$，请找到数列 $A$ 的 $m$ 个互相不相交的子段（$A[x 1 : y 1], A[x 2 : y 2], \cdots, A[x m : y m]$），使得 $\sum {k=1}^m \text{sum}(x k, y k)$ 的值最大。 输入格式 输入包含 2 行： 第 1 行为 2 个整数 $m$ 和 $n$； 第 2 行为 $n$ 个整数 $a 1, a 2, \cdots, a n$，用来表示数列 $A$。 输出格式 输出仅 1 行：$\sum {k=1}^m \text{sum}(x k, y k)$ 的最大值。 数据范围 $1 \leq n \leq 2000000$ $-50000 \leq a i \leq 50000$ 输入样例1 2 9 -1 -2 10 -3 7 -4 5 -9 3 输出样例1 19