Minimize Maximum Stick Segment Sum

You are given n wooden sticks with lengths \(L_i\) for \(i=1, 2, \dots, n\). The sticks are connected in order (the 1st stick is on the far left, followed by the 2nd, and so on) by \(n-1\) connections. You are allowed to cut at most \(m\) of these connections. After cutting, the sticks are divided into several contiguous segments. For each segment, its total length is the sum of the lengths of the sticks it contains.

Your task is to choose where to cut (possibly cutting fewer than \(m\) connections) so that the maximum segment sum among all segments is minimized. Let \(X\) be this minimized maximum segment sum. Additionally, count the number of ways to achieve this value. Since the answer can be large, output the count modulo \(10007\).

Input and Output Format: See below.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of sticks and the maximum number of cuts allowed). The second line contains \(n\) integers \(L_1, L_2, \dots, L_n\), where \(L_i\) represents the length of the \(i^{th}\) stick.

outputFormat

Output two integers separated by a space. The first integer is the minimized maximum segment sum \(X\) and the second integer is the number of ways to achieve \(X\) (modulo 10007).

sample

5 2
1 2 3 4 5

6 1