背景

我们能见到的第二可怕的事情,一定就是小学生放学了!

描述

小学生要放学了!MT学校一共有N个小学生,学校旁边的ET小卖部希望在小学生放学之前做好坑蒙小学生的准备!ET小卖部一共有M个不同的商品,每个商品的价格可以定位任意非负整数,且商品的价格两两不同,每个商品的数量是无限的。每个小学生有Ci RMB,他们希望购买尽量多的不重复的商品。由于小学生们必须节约用钱才能被评选为“综合评价全优生”,当有多种能购买同样多的物品的方案时,他们愿意花掉尽量少的钱。请问小卖部应该如何设定每个商品的价格,使得他们坑蒙小学生的收入尽可能多呢?他们还想知道,有多少种设置商品价格的方案,可以使得他们坑蒙小学生的收入最多呢?如果方案数大于101000,则输出-1,否则输出方案数对109+9取模的值。

输入格式

第一行两个用空格隔开的整数N,M。

紧接着N行,第i+1行一个整数,表示Ci(见题目描述)

输出格式

第一行一个整数,表示最多的收入;

第二行一个整数,如果方案数大于101000,则输出-1,否则输出方案数对109+9取模的值。

样例输入

5 3
1
3
5
7
9

样例输出

21
12

样例解释

三个商品的价格分别设置为2RMB、3RMB、4RMB。

第一个小学生由于没有足够的RMB,不购买任何商品;

第二个小学生只能购买2RMB的商品;

第三个小学生和第四个小学生可以购买2RMB和3RMB的商品;

第五个小学生可以购买三个2RMB、3RMB和4RMB的商品。

2 + (2 + 3) * 2 + 2 + 3 + 4 = 21,所以这种方案获得了21RMB的收入。

可以证明,没有更优的方案。

可以获得21RMB收入的方案一共有12个:

(1, 2, 4), (1, 4, 2), (2, 1, 4), (2, 4, 1), (4, 1, 2), (4, 2, 1),

(2, 3, 4), (2, 4, 3), (3, 2, 4), (3, 4, 2), (4, 2, 3), (4, 3, 2)。

数据范围与约定

对于100%的数据,1 <= Ci <= 1000,1 <= N <= 10000,1 <= M <= 40。

单点时间限制2s。

来源

原创