数列求和2

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给出一个数列 S 1, S 2, S 3, S 4 ... S x, ... S n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S x ≤ 32767). 我们定义 sum(i, j) = S i +S i+1+ ... + S j (1 ≤ i ≤ j ≤ n).

现在给你一个整数 m (n>=m > 0), 你的任务是找出m对 i,j 使 sum(i 1, j 1) + sum(i 2, j 2) + sum(i 3, j 3) + ... + sum(i m, j m) 最大化 (i x ≤ i y ≤ j x 或 i x ≤ j y ≤ j x 是不允许的).
结果仅输出sum(i x, j x)的最大累加和(1 ≤ x ≤ m) 就行了.

Input

包含多组数据,每组数据占一行,前两个整数是m和n,后面紧跟着是n个整数S 1, S 2, S 3 ... S n.

Output

输出所描述的结果,每一组的结果占一行

Sample Input

1 3 1 2 3 
2 6 -1 4 -2 3 -2 3

Sample Output

6
8

Hint

Source

“师创杯”山东理工大学第八届ACM程序设计竞赛