시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

Gug is preparing a feast for his friends. The feast consists of N plates of food arranged in a single row, with the ith plate from the left giving Ai points of satisfaction if eaten. As some plates of food might be rotten, it is possible that Ai is negative.

There are a total of K people involved in the feast, and each person will be assigned a consecutive segment of plates to consume. This segment can possibly be empty. The segments of two people cannot overlap, as food cannot be eaten twice. Gug wishes to assign the plates to his friends such that the sum of satisfaction points of all the plates of food consumed is maximised.

입력

Your program must read from standard input.

The input starts with a line with two integers N and K.

The next line will contain N integers A1, . . . , AN.

출력

Your program must print to standard output.

The output should contain a single integer on a single line, the sum of satisfaction points in an optimal assignment.

제한

  • 1 ≤ K ≤ N ≤ 3 × 105
  • 0 ≤ |Ai| ≤ 109

예제 입력 1

6 1
1 -2 3 -1 5 -6

예제 출력 1

7

It is optimal to assign the only person to the segment [3, -1, 5].

예제 입력 2

6 2
1 2 3 -10 5 6

예제 출력 2

17

Picking the consecutive segments [1, 2, 3] and [5, 6] is the most optimal solution.

예제 입력 3

6 4
-1 -2 -1 0 -5 -1

예제 출력 3

0

As all the satisfaction points are non-positive, it is optimal to choose empty segments for all four people.