军营装备库的组合配置

题目描述

王国边境的防御战即将打响，作为军需官的你需要从装备库中挑选物资，为前线士兵配置最强力的装备组合。

装备库里存放着三类装备：

• 传说装备：每件都是独一无二的宝物，总共只有一件，一旦分配就无法再获得。这些装备拥有最强大的属性加成。

• 制式装备：军工厂批量生产的标准装备，可以无限供应。虽然单件属性一般，但胜在稳定可靠。

• 限量装备：从友邦进口的特种装备，由于外交协议限制，每种最多只能申请有限数量。这些装备往往有特殊的战术价值。

现在你的运输车队载重上限为 $W$，需要在三类装备中做出选择。每种装备都有重量和战斗力加成值。你的目标是让整支部队的战斗力总和最大化。

输入格式

第一行包含四个整数 $a$, $b$, $c$, $W$，分别表示传说装备的种类数、制式装备的种类数、限量装备的种类数和载重上限。

接下来 $a$ 行，每行两个整数 $w_i$ 和 $v_i$，表示第 $i$ 种传说装备的重量和战斗力。

接下来 $b$ 行，每行两个整数 $w_i$ 和 $v_i$，表示第 $i$ 种制式装备的重量和战斗力。

接下来 $c$ 行，每行三个整数 $w_i$, $v_i$, $k_i$，表示第 $i$ 种限量装备的重量、战斗力和数量限制。

输出格式

输出一个整数，表示能获得的最大战斗力总和。

输入输出样例 #1

输入 #1

1 1 1 15
6 10
3 4
4 6 2

输出 #1

22

样例解释 #1

最优方案：

• 选择传说装备（重量6，战斗力10）
• 选择1份制式装备（重量3，战斗力4）
• 选择2份限量装备（重量4×2=8，战斗力6×2=12）
• 总重量：6 + 3 + 8 = 17 > 15，不行

重新计算：

• 选择传说装备（重量6，战斗力10）
• 选择3份制式装备（重量3×3=9，战斗力4×3=12）
• 总重量：6 + 9 = 15
• 总战斗力：10 + 12 = 22

这是最优解。

数据范围

• $0 \leq a, b, c \leq 100$
• $1 \leq a + b + c \leq 100$
• $1 \leq W \leq 1000$
• $1 \leq w_i \leq W$
• $1 \leq v_i \leq 1000$
• $1 \leq k_i \leq 100$

对于 $20\%$ 的数据，$b = c = 0$（只有传说装备）。

对于 $20\%$ 的数据，$a = c = 0$（只有制式装备）。

对于 $20\%$ 的数据，$a = b = 0$（只有限量装备）。

建议

一刷：掌握三种背包的统一处理框架，理解每种背包的遍历顺序差异。

二刷：熟练运用二进制优化处理多重背包部分，优化整体算法效率。

三刷：思考如何处理更复杂的混合情况，如依赖关系、分组限制等。