$($Method $1)$

$$ Take the scores of n students as input, sort them in descending order,

and then divide them into k groups.

$$ Assume that the lower group numbers correspond to higher scores.

$$ Starting from i $=1$ up to k$-1,$ calculate the differences between the

minimum score of the i

th group and the maximum score of the $($i$+1)$th

group, and maximize the sum of these differences.

$$ However, each group must have at least one student

Input

$$ Take input from standard input.

$$ The first line contains n and k$.$

$$ The next line contains the scores of n students in ascending order of

enrollment numbers.

$$ Here, n is a number greater than or equal to k$.$

$$ Each score can range from $0$ to $1,000,$ and ties are possible.

$$ Surprisingly, n can be as large as $104.$

$$ k is a positive integer less than or equal to $12.($Note: depending on the

school, each grade $($A$,$ B$,$ C$,$ D$)$ may be divided into $2$ or $3$ categories$)$

Output

$$ Print to standard output and write to files simultaneously.

$$ Print the $($maximum$)$ sum of differences in Method $1$ on the first line

of standard output.

$$ Write the groups from Method $1$ to a file $($filename: Partition$1.$txt$).$

The first line of the file corresponds to Group $1,$ and the kth line

corresponds to Group k$.$ Each line lists "student number $($student

score$)"$ in ascending order of student numbers.

$$ Input $($standard$/$console input$)$

$153$

$50851035451575802530556065705$

Output $($standard$/$console output$)$

$20$

Output $($filename: Partition$1.$txt$)$

$1(50)2(50)5(50)7(50)8(50)11(50)12(50)13(50)14(50)$

$4(20)9(20)10(20)$

$3(10)6(10)15(10)$