|
An experienced Nanny knows that mischievous children can never stay quiet. To keep the children busy, Eva has decided to let the children play a game:
Given consecutive pairs of rods, A0 with A1, A1 with A2, An - 2 with An - 1, the children must separate the pairs into two disjoint sets of these rods.
Eva allows the children to make a maximum of K separations. The objective of the game is to try to separate the rods, such that the longest rod in one of the sets is as short as possible.
During the games, children have given various different optimal solutions. Please help her! She wants you to help her to calculate the length of the longest rod, as well as the number of ways of obtaining this length mod 10007.
There is a number of inputs. The first line is n, the number of rods, and k, the number of separations allowed. ( 0<= n <= 50000,0 <= k <= 1000). The length of the n rods follows on the next line. ( 0 <= Ai <= 20000 ).
On a single line output the length of the longest rod that is as short as possible, followed by the number of ways of obtaining it.
| Sample Input | Sample Output |
10 5 3 2 1 3 5 8 3 2 1 2 3 2 1 1 10 |
8 31 10 2 |
Problemsetter: Rodrigo Burgos Domínguez