시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB3781209231.615%

문제

N개의 정수로 이루어진 수열이 주어진다. 주어진 수열에서 연속된 1개 이상의 수로 이루어진 부분 수열을 "그룹"이라고 하자. 양의 정수 M이 주어졌을 때 M개의 그룹을 선택해서 그룹에 속한 모든 수의 합의 최댓값을 구하는 프로그램을 작성하라.

입력

첫째 줄에 N과 M(1 ≤ M ≤ N ≤ 20)이 주어진다. 둘째 줄에는 수열에 속한 수가 주어진다. 수는 공백으로 구분되어져 있고, 절댓값이 100보다 작거나 같은 정수이다.

출력

첫째 줄에 M개의 그룹을 선택했을 때, 그룹에 속한 모든 수의 합의 최댓값을 출력한다.

예제 입력 1

10 2
10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1

54

예제 입력 2

10 3
10 -4 3 1 5 6 -35 12 21 -1

예제 출력 2

58