思路：贪心

为了使得总和最大，每次操作一定是让最大值和次大值相乘，然后将得到的结果作为最大值，再进行计算，直到执行$m$次。

实际操作中可以对原数组进行排序，然后按照上述方式模拟即可。

数据范围较大，C++和Java选手需要注意爆int

时间复杂度

题目内容

小美被给定一个长度为$n$的数组，她最多可以进行$m$次操作，每次操作如下:

1.选择两个下标 $i,j(1 <i< j< n)$

2.选择两个整数$x,y$ 满足条件：$x*y = a_i*a_j$

3.$a_i:=x$ , $a_j:=y$

他只能操作$m$ 次 ， 目标是使得最后数组中的元素的总和尽可能大

输入描述

一行两个整数$n,m$ , 表示数组长度和操作次数

一行$n$个整数 $a_1,a_2,...,a_n$

$1\leq m<n \leq 1e5$

$1 \leq a_i \leq 1e5$

输出描述

输出一个整数，表示最后数组中元素总和最大值。

由于答案可能很大，输出取模$1e9 + 7$ 意义下的结果

样例

输入

6 2
1 2 3 4 5 6

输出

128