509005 - 集合

【题目描述】集合(set)

有一个大小为n的可重集S,每次操作可以加入一个数 a+b(a,b均属于S),求k次操作后它可获得的S的和的最大值(数据保证这个值为非负数)。

输入

第一行有两个整数n,k表示初始元素数量和操作数,第二行包含n个整数表示初始时可重集的元素。

输出

输出一个整数,表示和的最大值。答案对10000007取模。

样例

输入

2 2
3 6

输出

33

提示

【数据范围】 对于30%的数据,有n≤10^5,k≤10^5,|ai|≤10^5。 对于100%的数据,有n≤10^5,k≤10^9,|ai|≤10^5

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题