题目描述

有 $n$ 根木棍，第 $i$ 根木棍的长度为 $L_i$，$n$ 根木棍依据编号次序（即最左边是第 $1$ 根木棍，然后是第 $2$ 根木棍，以此类推）连接在一起，总共有 $n-1$ 个连接处。现在允许你最多砍断 $m$ 个连接处，砍完后 $n$ 根木棍被分成了很多段，要求满足总长度最大的一段长度最小。

输出总长度最大的一段长度的最小值，并且输出使总长度最大的一段长度最小的方案总数除以 $10007$ 的余数。

输入格式

第一行，两个正整数 $n,m$。

接下来 $n$ 行，第 $i$ 行一个正整数 $L_i$，表示第 $i$ 根木棍的长度。

输出格式

输出 $2$ 个整数，第一个整数是总长度最大的一段长度的最小值，第二个整数是使总长度最大的一段长度最小的方案总数除以 $10007$ 的余数。

3 2                           
1 
1
10

10 2

提示

样例解释

可以砍 $1$ 下分成 $1,1$ 和 $10$ 两个部分，也可以砍 $2$ 下分成 $1$、$1$ 和 $10$ 三个部分。

数据范围

对于所有的数据，$n \le 50000,\ 0\le m\le \min(n-1,1000),\ 1\le L_i\le 1000$。