Description

There are $n$ sticks. The length of the $i$-th stick is $L_i$. The $n$ sticks are connected in the order of their indices (that is, the leftmost is the $1$-st stick, then the $2$-nd stick, and so on). There are $n-1$ joints in total. You are allowed to cut at most $m$ joints. After cutting, the $n$ sticks are divided into several segments. The requirement is to minimize the length of the longest segment.

Output the minimum possible value of the length of the longest segment, and the remainder of the number of schemes that achieve this minimum when divided by $10007$.

Input Format

The first line contains two positive integers $n, m$.

The next $n$ lines each contain a positive integer $L_i$, representing the length of the $i$-th stick.

Output Format

Output $2$ integers: the minimum possible value of the length of the longest segment, and the remainder of the number of schemes that achieve this minimum when divided by $10007$.

3 2                           
1 
1
10

10 2

Hint

Sample Explanation

You can cut once to split into two parts of total lengths $1, 1$ and $10$, or cut twice to split into three parts of total lengths $1$, $1$, and $10$.

Constraints

For all testdata, $n \le 50000,\ 0 \le m \le \min(n-1, 1000),\ 1 \le L_i \le 1000$.

Translated by ChatGPT 5