小Z的团队成功获得了病毒的RNA。在进一步分析之前，他们要得到RNA的最大饱浓度。
具体地讲，每份检测过后的病毒样本都含有一定浓度的RNA。病毒样本若合并到一起，会有如下的规则：浓度为x和浓度为y的样本会创造出浓度为x+y+xy的样本。
现在小Z的团队想要知道，若将n份样本中k份样本依次合并（只能是合并k-1次的样本与原样本合并），那么得到的浓度最大为多少？
第一行两个整数n和k，用空格隔开。
第二行共n个正整数，表示病毒原样本的浓度，用空格隔开。
一行一个整数表示答案。
【样例1输入】
3 2
1 2 3
【样例2输入】
4 4
1 1 1 1
【样例3输入】
5 3
9 5 1 3 7【样例1输出】
11
【样例2输出】
15
【样例3输出】
479
【样例1解释】
将2和3合并，答案为2*3+2+3=11。
【样例2解释】
不管怎么合并，每次都是和浓度为1的合并。因此答案为1+1+1*1=3,1+3+1*3=7,1+7+1*7=15。
【数据范围】
对于20%的数据，所有数字都相等。
对于另外30%的数据，n<=6。
对于另外30%的数据，n<=1000，分别有10%的数据k=1,2,3
对于100%的数据，n<=100000，k<=5，最后的答案在long long范围内。