装箱问题

云计算资源的供应属于在线动态多维向量装箱问题，装箱问题的核心在于最优化剩余大规格可发放量，提升装箱效率。客户的需求往往可以通过多种虚拟机规格组合实现，这使得实现的方式更加灵活。如何在客户需求多种虚拟机规格组合的场景下，选出剩余大规格可发放量最优的方案，也对装箱算法提出了挑战。

在本题中，为了简化计算，我们只考虑两种规格的物品，其体积分别为 $x$ 和 $y$，每种物品可以看作有无数个。之后，给出 $n$ 个空箱子，第 $i$ 个空箱子最多可容纳 $B_i$ 的体积。为了满足客户的需求，我们需要往这 $n$ 个箱子里一共装入不少于 $r$ 个单位体积的物品，而在满足客户需求的同时，尽可能使剩余的大规格可发放量最大化。

形式化地说，设 $C_i$ 表示第 $i$ 个箱子的剩余体积，那么需要满足以下条件：

$$
\sum\limits_{i=1}^{n}B_i - C_i \ge r
$$

满足上述条件的基础上，我们需要最大化如下式子：

$$
\sum\limits_{i=1}^{n}C_i^2
$$

本题只需要求出这个最大值即可。

第一行一个正整数 $T$，表示有 $T$ 组数据。

对于每一组数据，第一行输入四个正整数 $n, x, y, r$。第二行输入 $n$ 个正整数 $B_1,B_2,\ldots, B_n$。

• $2 \le n, x, y \le 100$


• $2 \le B_i \le 100$


• $2 \le r \le \sum_{i=1}^n B_i$


• $\sum n \le 200$

对于每一组数据，输出一行一个整数。如果无法满足客户需求，输出 $\texttt{-1}$；否则，输出该式子的最大值。

	
3
3 2 3 10
7 8 9
5 3 5 11
2 3 4 5 6
5 7 2 19
2 3 4 5 6

106
41
-1

第一组数据，$C_1 = 0, C_2 = 5, C_3 = 9$，总和为 $0^2 + 5^2 + 9^2 = 106$。

2023 CCPC 华为云计算挑战赛