#P1495. 2023.08.26-MT-第三题-塔子哥的数组

2023.08.26-MT-第三题-塔子哥的数组

题目内容

塔子哥被给定一个长度为nn的数组，她最多可以进行mm次操作，每次操作如下:

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

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

3.ai:=xa_i:=x , aj:=ya_j:=y

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

输入描述

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

一行nn个整数 a1,a2,...,ana_1,a_2,...,a_n

1≤m<n≤1e51\leq m<n \leq 1e5

1≤ai≤1e51 \leq a_i \leq 1e5

输出描述

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

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

样例

输入

6 2
1 2 3 4 5 6

输出

128

知识点:*****

查看知识点以及同类型题目

Statistics