The solution was made by Furina ❤️

前言

首先，我们拿到一道问题，在读懂题意后，我们应该去观察本题的数据范围，通常在$CSP-J/S$或$NOIP$中，数据范围对本题所需采用的时间复杂度（引导算法）具有一定的提示性，即使无法想到正解，对部分分的获得也大有裨益，说不定，各位同学就能在思考部分分的过程中，逐步发掘正解的真相呢！

🚀️ 下面是一般的数据范围所对应的时间复杂度(仅供参考，在赛场需随机应变)：

$1<=n<=12$ $O(n!)算法，一般对应全排列类型的算法$

$1<=n<=20$ $O(2^n)算法，一般是bfs,dfs$

$1<=n<=500$ $O(n^3)算法$

$1<=n<=5*10^4$ $O(n^2)算法$

$1<=n<=1*10^5$ $O(nlogn)算法，在超过5*10^5的数据范围中使用时应注意卡常！$

$1<=n<=10^6$,$O(n)算法$

$1<=n<=10^{12}$,$O(\sqrt{n})算法$

$1<=n<=10^{18}$,$O(logn)算法，一般是二分$

$n>=10^{18}$,$O(1)算法，一般为数学公式推导$

20分

$20pts$中$1<=n,m<=12$,提示说我们需要使用搜索之类的算法。

注意到我们对于每一个数之间的操作，分为两种，一种是保留原数，第二种是修改为$w$，进行dfs操作，对每个数可能的两种情况进行搜索，修改超过$m$次进行回溯操作，修改的过程中统计和的最大值即可。

时间复杂度为$O(T2^n)$。

50分

在$1<=n,m<=7000$的数据范围中，我们需要采用更优秀的$**O(n^2)**$类型的算法。

我们需要采用贪心算法，顾名思义，贪心算法就是取出当前对我们最有利的答案进行转化，一般需要进行数学证明（但是在赛场上建议只猜不证），适用于对于每一个规模较小的子问题，我们的操作必须满足局部最优性，而这也是贪心算法的弊端：目光短浅（如需解决请采用动态规划算法，这里不再赘述）

对于每一个数（以下假定为$x$），我们有三种情况需要进行讨论：

①$x>w$,此时若将$x$修改为$w$会减少序列和的大小，故我们不修改；

②$x=w$,此时若将$x$修改为$w$不会减少序列和的大小，但也不会增大，为了节省修改次数，故我们依旧不修改；

③$x<w$,此时若将$x$修改为$w$会增大序列和的大小， 但因操作次数有限，我们只能选择对增加序列和贡献最大的值进行修改，即取出$w-x$最大的值进行修改。

容易想到，对于该序列中$w-x$的最大值，即为该序列的最小值（证明显然），我们可以每次操作时，对于该序列中最小的数决定其是否修改，产生的贡献为$max(0,w-x)。$

我们怎么做到每次取出序列的最小值呢？可以采用打擂台的方法,每次进行序列的遍历,进行比较即可。

时间复杂度为$O(Tmn)。$

100分

对于$1\le n,m\le 5*10^5$的数据范围，$O(n^2)$类型的算法已经不够优秀，相对应地，我们需要对其进行优化，成为$O(nlogn)$类型的算法。

我们可以显然发现，我们已经无法再对我们的贪心策略做出进一步的实质性的优化，所以我们只能从每次取出序列的最小值做出进一步的优化。

发现我们每次遍历序列，只是为了取出整个序列的最小值进行修改，取出最小值，我们可以使用各式各样的排序算法，根据数据范围进行选择，插入排序、冒泡排序均为$O(n^2)$的排序方法，无法进行优化，而桶排序无法支持负数，即便通过数组的平移进行解决，在本题的空间下仍会导致$MLE$。

综上，我们可以采用快速排序或优先队列进行（消耗空间较严重）优化(在C++中有内置函数),较为方便。（不会快速排序或优先队列的请Google一下，非常的重要！！！）

时间复杂度为O(Tnlogn)，可以通过本题。

写在最后

首先，本题部分选手获得$5$分的原因是没有使用$long long$($OI$上有俚语“十年OI一场空，不开long long 见祖宗”的说法)，十分可惜。在赛场上，建议无脑开long long，以免不必要的分数损失。

本题需要开long long的原因是$-10^9 \le a_i \le 10^9$,$1 \le n,m \le 10^5$,处理的数据量已经达到了$10^{14}$,超过了int型的存储范围。

还有，请在每一次比赛时的最后几分钟检查一下文件读写！

不会文件读写的看下面：

freopen("文件名.in","r",stdin);

freopen("文件名.out","w",stdout);

好啦，美丽的$Furina$小姐要继续去守护枫丹的人们了，期待下次相遇！

//其实这题只是个非常简单的贪心+排序而已啦，签到题
//但是十年OI一场空，不开long long见祖宗 100pts->5pts是每个OIer必经的一环呢 
//各位参赛的同学们，你们完成Furina小姐的考验了吗
//祝各位同学OI生涯一路顺风！
//以下是本题的std:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+2;
#define ll long long
ll T,n,k,w,a[N];
int main(){
//	freopen("furina.in","r",stdin);
//	freopen("furina.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		ll ans=0;
		cin>>n>>k>>w;
		for(int i=1;i<=n;++i)cin>>a[i];
		sort(a+1,a+n+1);//快速排序函数
		for(int i=1;i<=n;++i){
			if(a[i]<=w&&i<=k)ans+=w;
			else ans+=a[i];
		}
		cout<<ans<<'\n';
	}
	return 0;
}
//made by Furina