P1049糖果店（candy）

【题目描述】

小 X 的糖果店中有 $n$ 颗糖果，其中第 $i$ 颗糖果的价格为 $a_i$ 元。小 R 带着 $m$ 元来到糖果店，可以任意选择若干颗糖果购买。

为了让顾客能够一次品尝两种口味，小 X 准备了至多 $k$ 个双糖礼盒。每个双糖礼盒必须装入两颗已经购买且没有装入其他双糖礼盒的糖果。装入同一个双糖礼盒的两颗糖果不再分别结算，这个双糖礼盒的价格等于其中较贵糖果的价格。没有装入双糖礼盒的糖果仍按原价结算。

小 R 希望购买的糖果尽可能多，同时支付的总费用不能超过 $m$ 元。

你需要求出小 R 最多能够购买多少颗糖果。

【输入格式】

本题包含多组测试数据。

从文件 $\textbf{\textit{candy.in}}$ 中读入数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据。对于每组测试数据：

第一行包含三个非负整数 $n,m,k$，分别表示糖果数量、小 R 拥有的钱数与最多能够使用的双糖礼盒数量。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示第 $i$ 颗糖果的价格。

【输出格式】

输出到文件 $\textbf{\textit{candy.out}}$ 中。

对于每组测试数据，输出一行一个非负整数，表示小 R 最多能够购买的糖果数量。

【样例 1 输入】

10 225 11 132 4 7 3 646 16 258 5 6 3 4 9

【样例 1 输出】

1425

【说明/提示】

【样例 1 解释】

对于第一组测试数据，小 R 可以购买价格分别为 $2,3,4,6$ 元的四颗糖果，并将价格为 $4,6$ 元的两颗糖果装入一个双糖礼盒。总费用为 $2+3+6=11$ 元。

可以证明，购买五颗糖果至少需要 $16$ 元，因此答案为 $4$。

对于第二组测试数据，小 R 可以购买价格分别为 $3,4,5,6,8$ 元的五颗糖果，将价格为 $4,5$ 元与价格为 $6,8$ 元的糖果分别装入两个双糖礼盒，并单独购买价格为 $3$ 元的糖果。总费用为 $3+5+8=16$ 元。

可以证明，购买六颗糖果至少需要 $20$ 元，因此答案为 $5$。

【样例 2】

见选手目录下的 $\textbf{\textit{candy/candy2.in}}$ 和 $\textbf{\textit{candy/candy2.ans}}$。

该附加样例满足测试点 $1\sim 3$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{candy/candy3.in}}$ 和 $\textbf{\textit{candy/candy3.ans}}$。

该附加样例满足测试点 $4\sim 6$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{candy/candy4.in}}$ 和 $\textbf{\textit{candy/candy4.ans}}$。

该附加样例满足测试点 $10\sim 15$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{candy/candy5.in}}$ 和 $\textbf{\textit{candy/candy5.ans}}$。

该附加样例满足测试点 $16\sim 20$ 的数据范围。

【数据范围】

设 $N$ 为单个测试点内所有测试数据的 $n$ 之和。

对于所有测试数据，保证：

• $0\leq c\leq20$，$1\leq T\leq2\times10^4$。
• $1\leq n\leq2\times10^5$，$N\leq5\times10^5$。
• $0\leq k\leq\lfloor n/2\rfloor$。
• $0\leq m\leq10^{18}$。
• 对于所有 $1\leq i\leq n$，均有 $1\leq a_i\leq10^9$。