꿀벌

좌우로 $N$ 개의 구역이 있는 벌판이 있다. 이 벌판의 제일 왼쪽 구역에는 벌집이 하나 있고 $K$ 마리의 벌들이 살고 있다.

여름 동안 벌들은 각자 서로 다른 주거 구역을 하나 잡아서 따로 살기로 했다. 벌집이 있는 구역도 주거 구역으로 잡을 수 있다. 가을이 된 어느 날 벌들은 모두 집으로 모이기로 했다. 각 벌은 왼쪽으로 똑바로 이동해서 벌집으로 간다.

각 구역의 꿀의 밀도를 알고 있다. 한 벌이 집으로 이동하는 과정에서 거치는 모든 구역에서 밀도 만큼의 꿀을 따서 집으로 이동한다. 단, 그 구역이 어떤 벌의 주거 구역이라면 꿀을 전혀 딸 수 없다. 한 구역을 여러 벌이 지나는 경우 모든 벌이 밀도 만큼의 꿀을 딸 수 있다. 벌집이 있는 제일 왼쪽 구역에서도 (그 구역이 주거 구역이 아니라면) 마찬가지이다. 벌의 주거 구역에서는 어떤 벌도 꿀을 딸 수 없다는 것에 주의하라.

아래 <그림 1>와 같이 꿀의 밀도가 주어졌다고 하고 벌의 마릿수 $K = 2$라고 하자. 주거 구역을 제일 오른쪽의 두 구역으로 잡는 경우 딸 수 있는 꿀의 양은 $(2+3+2+1) + (2+3+2+1) = 16$이다. 하지만, 주거 구역을 제일 오른쪽과 거기서 한 구역 떨어진 왼쪽 구역으로 잡는 경우 딸 수 있는 꿀의 양은 $(2+3+2) + (2+3+2+8) = 22$이다.

구역들의 꿀의 밀도를 입력으로 받아 $K$ 마리의 벌들이 딸 수 있는 가장 많은 꿀의 양을 계산하는 프로그램을 작성하라.

입력 형식

첫 줄에 구역의 개수를 나타내는 정수 $N$과 벌의 수를 나타내는 정수 $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 2\, 000;$ $1 \le K \le N$)

두 번째 줄에 왼쪽 구역부터 각 구역의 꿀의 밀도를 나타내는 $N$ 개의 정수가 공백으로 구분되어 주어진다. 꿀의 밀도 값은 $1$ 이상 $10^9$ 이하이다.

출력 형식

$K$ 마리의 벌들이 딸 수 있는 가장 많은 꿀의 양을 출력한다.

예제

6 2
2 3 2 1 8 6

22

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설