Team 7

All submissions for this problem are available.
Team 7 consisting of Naruto, Sasuke and Sakura is the base of the Leaf Village. This team got divided initially but eventually they all came along in the 4th Shinobi World War. They were the only reason for their victory. After their victory, the Leaf Village started to prosper but soon a new problem arose.
The problem was education for The New Generation. There were a total of N students seeking education. Each student has a different chakra level, i^{th} student of which has a chakra level A_{i}. These students are arranged in the form of an array A, i^{th} element of which denotes the chakra level A_{i} of the i^{th} student. The Leaf Village administration thought of a method to deal with this education problem which was to divide these students into K nonempty groups (of varying sizes) as currently they had only K teachers available.
Formally, the task is to partition the array A (of chakra levels of students) into exactly K nonempty subarrays. Now the partition should be done in such a way that the sum of the minimum chakra levels of each of the K groups is maximum. As the entire village is busy with the renovation work of the village, so can you help them calculate this maximum sum.
Input
The first line of input contains two spaceseparated integers N and K denoting the number of students and the number of teachers (or the number of parts into which the array has to be partitioned).
The next line contains N spaceseparated integers denoting the array A (the array that has to be partitioned into K parts), i^{th} element of which is the chakra level of the i^{th} student.
Output
The output should consist of a single integer corresponding to the answer of the problem.
Constraints
 1 ≤ N ≤ 5000
 1 ≤ K ≤ N
 1 ≤ A_{i} ≤ 10^{9}
Information to Score Partial Points
 For 5% of the score, it is guaranteed that K = 2 and N ≥ 2.
 For further 5% of the score, it is guaranteed that N ≤ 10.
 For further 10% of the score, it is guaranteed that N ≤ 100.
 For further 15% of the score, it is guaranteed that N ≤ 500.
 For the rest of the 65% of the score, no extra guarantees. That is, N ≤ 5000.
Example
Input: 5 3
1 5 9 2 3 Output: 12
Input:
6 3
4 5 9 2 3 7
Output:
15
Explanation
Example case 1. The most optimal way to divide the array into exactly 3 subarrays such that the sum of minimum values of these 3 subarrays is maximum is [1,5], [9] and [2,3] for which the sum is 1+9+2=12.
Example case 2. The most optimal way to divide the array into exactly 3 subarrays such that the sum of minimum values of these 3 subarrays is maximum is [4,5], [9] and [2,3,7] for which the sum is 4+9+2=15.
Author:  mohitbindal644 
Tags  mohitbindal644 
Date Added:  17022018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions