P4674. 最优折扣组合

场次：2026年3月28日-开发岗 · 来源：CodeFun2000 P4674

题目描述

你是一家商店的经理，商店内共有 $n$ 件商品，第 $i$ 件商品的标价为 $p_i$。你手中有两种不同类型的优惠券：

• “半价券”：对一件商品使用后，该商品的价格变为 $\lfloor p_i / 2 \rfloor$（即除以 $2$ 并向下取整）。
• “固定减免券”：对一件商品使用后，该商品的价格变为 $p_i - k$（价格允许变为负数）。

每件商品最多可以被使用一次半价券，最多使用一次固定减免券（两种券可以同时用在同一种商品上）。你总共有 $a$ 张半价券和 $b$ 张固定减免券。

请你合理分配这些优惠券，使得所有商品的最终价格之和达到最小，并输出这个最小值。

约束条件

• 商品数量 $n$ 不超过 $2 imes 10^5$。
• 半价券数量 $a$ 和固定减免券数量 $b$ 均不超过 $n$。
• 减免额度 $k$ 不超过 $10^9$。
• 每件商品的初始标价 $p_i$ 不超过 $10^9$。
• 一个测试输入中所有测试数据的 $n$ 之和不超过 $4 imes 10^5$。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 2 imes 10^5$），表示测试数据的组数。

接下来对于每组测试数据：

第一行包含四个整数 $n, a, b, k$，含义如上所述。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，表示各商品的初始标价。

输出格式

对于每组测试数据，输出一行一个整数，表示经过最优使用优惠券后，所有商品的最终价格之和的最小值（该值可能为负数）。

示例

示例 1

输入：

1
4 2 1 5
10 3 8 12

输出：

17

说明：

该组商品初始总价为 10 + 3 + 8 + 12 = 33。 对每件商品使用半价券可减少 $\lceil p_i / 2 \rceil$，各商品半价收益分别为：10 减少 5，3 减少 2，8 减少 4，12 减少 6。我们有 a = 2 张半价券，应选择收益最大的两件商品：12 和 10，共减少 6 + 5 = 11。 我们还有 b = 1 张固定减免券，减少 k = 5。 因此最终价格总和为 33 - 11 - 5 = 17。

示例 2

输入：

1
3 0 2 4
7 8 9

输出：

16

说明：

该组没有半价券（a = 0），只能使用固定减免券。 初始总价为 7 + 8 + 9 = 24。 使用 b = 2 张固定减免券，每张减少 k = 4，共减少 8。 最终价格总和为 24 - 8 = 16。

示例 3

输入：

2
1 1 1 100
50
2 0 0 10
100 200

输出：

-75
300

说明：

第一组：只有一件价格为 50 的商品。半价券收益为 $\lceil 50/2 \rceil = 25$，固定减免券收益为 k = 100。最终价格为 50 - 25 - 100 = -75。 第二组：有两件商品，但没有优惠券（a = 0，b = 0）。初始总价 100 + 200 = 300，无法减免，最终总和仍为 300。

示例 4

输入：

1
2 2 1 1
1 1

输出：

-1

说明：

两件商品价格均为 1。半价券收益为 $\lceil 1/2 \rceil = 1$，用满 a = 2 张共减少 2。固定减免券一张，减少 k = 1。初始总价为 2，最终总和为 2 - 2 - 1 = -1。 该样例展示了最终总和可以为负数。