Problem 1024. -- Max Sum Plus Plus## HDU_1024: Max Sum Plus Plus

Time Limit: 1000 MS Memory Limit: 32 MB 64bit IO Format: %I64d

Submitted: 11 Accepted: 7

[Submit][Status][Web Board]## Description

Now I think you have got an AC in Ignatius.L's "Max Sum" problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.

Given a consecutive number sequence S_{1}, S_{2}, S_{3}, S_{4} ... S_{x}, ... S_{n} (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S_{x} ≤ 32767). We define a function sum(i, j) = S_{i} + ... + S_{j} (1 ≤ i ≤ j ≤ n).

Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i_{1}, j_{1}) + sum(i_{2}, j_{2}) + sum(i_{3}, j_{3}) + ... + sum(i_{m}, j_{m}) maximal (i_{x} ≤ i_{y} ≤ j_{x} or i_{x} ≤ j_{y} ≤ j_{x} is not allowed).

But I`m lazy, I don't want to write a special-judge module, so you don't have to output m pairs of i and j, just output the maximal summation of sum(i_{x}, j_{x})(1 ≤ x ≤ m) instead. ^_^

## Input

Each test case will begin with two integers m and n, followed by n integers S_{1}, S_{2}, S_{3} ... S_{n}.

Process to the end of file.

## Output

Output the maximal summation described above in one line.

## Sample Input

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

## Sample Output

## HINT

Huge input, scanf and dynamic programming is recommended.

[Submit][Status][Web Board]