分数: 366 分
问题陈述
高桥作为公司新业务的负责人,正在尝试选择要执行的项目 N 项目建议书。每个项目要么执行,要么不执行,同一个项目不能执行多次。也可以不选择任何项目。
执行每个项目 i (1 \leq i \leq N) 需要花费 C_i 一万日元,利润为 P_i 一万日元。这里,利润和成本是独立的值,目标是最大化总利润。成本仅与预算约束相关,不会从利润中扣除。
但是,某些项目对由于团队任务竞争或共享设备而相互冲突,并且无法同时选择。有 M 这种冲突关系,以及 j-th (1 \leq j \leq M) 冲突关系表明两个项目 U_j 和项目 无法同时选择 V_j 。
高桥的预算限额是 K 一万日元。求所选项目的最大总利润,使得所选项目的总成本最多为 K 一万日元且无冲突关系,两个项目同时选定。
换句话说,让 S 是所选项目的集合,找到最大值 \displaystyle\sum_{i \in S} P_i 须满足以下所有条件:
- \displaystyle\sum_{i \in S} C_i \leq K
- 对于所有人 j (1 \leq j \leq M), U_j 和 V_j 不都包含在 S (即 \{U_j, V_j\} \not\subseteq S)
如果未选择任何项目(即 S 为空集),总利润为 0.
约束
- 1 \leq N \leq 18
- 0 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq K \leq 10^5
- 1 \leq C_i \leq 10^5 (1 \leq i \leq N)
- 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
- 同一冲突关系不会被多次给出
- 所有输入均为整数
输入
N M K C_1 P_1 C_2 P_2 \vdots C_N P_N U_1 V_1 U_2 V_2 \vdots U_M V_M
- 第一行包含三个空格分隔的整数: N 代表项目数量, M 代表冲突关系的数量,以及 K 代表预算限制。
- 从第 2 行到 (N + 1)第行,给出了每个项目的信息。
- 的 (1 + i)第行 (1 \leq i \leq N) 包含成本 执行项目需要 C_i 执行项目所需的 i 和利润 获得 P_i ,以空格分隔。
- 从 (N + 2)第 行 (N + M + 1)第行,给出了有关冲突关系的信息。如果 M = 0,这部分不存在。
- 的 (N + 1 + j)第行 (1 \leq j \leq M) 包含项目编号 U_j 和 V_j 参与 j第一个冲突关系,用空格分隔。
输出
在单行上以整数形式输出所选项目的最大总利润。
示例输入 1
3 1 100 50 80 60 90 40 50 1 2
示例输出 1
140
示例输入 2
5 3 200 30 100 50 150 40 120 60 200 80 180 1 2 2 3 4 5
示例输出 2
420
示例输入 3
8 6 500 100 500 80 400 120 600 90 450 70 350 110 550 60 300 150 800 1 2 1 3 2 4 3 4 5 6 7 8
示例输出 3
2350