잔치

시간 제한1초메모리 제한512 MB

요약

배열 A에서 서로 겹치지 않는 최대 K개의 부분 배열을 골라 원소 합의 총합이 최대가 되도록 한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 그리디, 힙, 누적 합
정답자: 아직 제출이 없습니다

문제

Gug는 친구들을 위해 잔치를 준비한다. 잔치는 한 줄로 늘어놓은 N개의 음식 접시로 이루어지고, 왼쪽에서 i번째 접시를 먹으면 만족도 Ai를 얻는다. 상한 음식이 있을 수 있으므로 Ai는 음수일 수도 있다.

잔치에는 모두 K명이 참여하고, 각 사람은 연속한 접시 구간을 하나씩 맡아 먹는다. 이 구간은 비어 있을 수도 있다. 두 사람의 구간은 겹칠 수 없는데, 음식을 두 번 먹을 수는 없기 때문이다. Gug는 먹은 모든 음식 접시의 만족도 합이 최대가 되도록 친구들에게 접시를 배정하려고 한다.

입력

프로그램은 표준 입력에서 입력을 읽는다.

첫 줄에 두 정수 N과 K가 주어진다.

다음 줄에 N개의 정수 A1, ..., AN이 주어진다.

출력

프로그램은 표준 출력에 출력을 쓴다.

최적 배정에서의 만족도 합을 한 줄에 하나의 정수로 출력한다.

제한

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

예제3

예제 1
입력
```
6 1
1 -2 3 -1 5 -6
```
예상 출력
```
7
```
예제 2
입력
```
6 2
1 2 3 -10 5 6
```
예상 출력
```
17
```
예제 3
입력
```
6 4
-1 -2 -1 0 -5 -1
```
예상 출력
```
0
```