题目背景

「在真实的世界里，我们见识了太多必将凋零的花、无法躲避的雨、沉没已久的船……

「但在这些无奈之外，我认为，应该要有人相信——

「至少在戏剧之中，人是可以支配命运的。」 ——《戏中人》

题目描述

$Furina$究其一生，守护着枫丹的人们。

身为水神的$Furina$,偶尔也喜欢玩操作序列的游戏。

有一天，她想到了这样一个问题：

给定一个长度为$N$的序列，$Furina$可以操作$q$次，对于每次操作，$Furina$可以将序列内任意一个数$a_i$修改为$w$(美丽的$Furina$小姐偷偷告诉你：不一定要修改哦！）。在操作过程中，$Furina$想知道她能获得的该序列的和最大为多少。

因为$Furina$太可爱了，所以你需要回答她多次询问。

因为$Furina$还要去守护枫丹，所以希望你能在$1s$内告诉她所有答案。

输入格式

输入一个正整数$T$，表示数据组数。

接下来$T$组数据，每组数据的格式如下：

第一行包含一个整数$n,k,w$,依次表示序列的长度，操作的次数，修改后的值。

第二行包含$N$个整数，表示序列的每一个数$a_i$。

输出格式

输出共$T$行，每行一个整数，表示$Furina$所能得到的序列和的最大值。

输入输出样例

1
6 1 2
1 1 4 5 1 4

17

3
5 2 4
5 1 7 6 2 
2 1 5
7 4 
5 1 1
2 2 5 3 3

26
12
15

说明/提示

美丽的$Furina$小姐给大家出了一点部分分作为签到分。

对于20%的数据，满足$1 \le n,m \le 12$;

对于50%的数据，满足$1 \le n,m \le 7000$;

对于100%的数据，满足$1 \le n,m \le 10^5，1 \le T \le 10,-10^9 \le a_i \le 10^9$;

本题有多测