SP699 HKNAP - Huge Knap Sack

我们的国王赢得了艰苦的战役，如今这整片土地归我们所有。这片土地的特别之处在于有许多迷人的金像。国王希望尽可能多地将黄金带回他的宫殿。我们发现这里有 $N$ 种类型的雕像，令人难以置信的是，这些雕像的每一种数量都是无限的。第 $i$ 种类型的雕像重量为 $W[i]$ 单位，体积为 $V[i]$ 单位。国王想要最大化他能带回宫殿的黄金总量。为此，我们可以使用 $S$ 个袋子来运输这些金像，每个袋子的容量为 $Y$。所有袋子是独立装满金像的，但我们可以通过花费 $C$ 单位的黄金来缝合两个袋子。缝合三个袋子需要 $2 \times C$ 的黄金，因为需要进行两次缝合，以此类推。你的任务是计算国王可能获得的最大黄金净收益，即带回雕像的总重量减去缝合的费用。

第一行输入一个整数 $T$，表示测试用例的数量。 对于每个测试用例，输入包括： - 第一行：四个整数 $N$, $S$, $Y$ 和 $C$，分别表示雕像的种类数、袋子的数量、每个袋子的容积以及缝合两袋所需的黄金单位。 - 接下来的 $N$ 行中，每行包括两个整数 $W[i]$ 和 $V[i]$，分别表示第 $i$ 种雕像的重量和体积。

输出一个整数，表示国王能够获得的最大净收益。这个收益指的是运输到宫殿的总重量减去缝合花费后的黄金净重量。

- $1 \leq S \leq 1000$ - $1 \leq Y \leq 10^9$ - $1 \leq N \leq 1000$ - $1 \leq W[i] \leq 100$（对于所有 $i$） - $1 \leq V[i] \leq 18$ - 输出的结果可以用 64 位整数表示 - $1 \leq T \leq 20$ - 所有的 $W[i]$ 和 $V[i]$ 都是质数或等于 1。 **本翻译由 AI 自动生成**