分数: 433 分
问题陈述
高桥是一个工业园的经理,该工业园包括 N 很多。每批编号从 1 to N,以及一个能够存储多达 P_i 大量货物可建造成吨 i.
有一天,请求存储总共 M 工业园区吨货。高桥希望在满足下述条件的同时存储尽可能多的货物。
工业园有 K 走廊, i第走廊直接连接地块 U_i 和很多 V_i。在由走廊直接连接的两个地块上同时建造仓库是 禁止,因为送货卡车的路线会互相干扰。如果两个地块没有通过走廊直接连接,那么仓库可以同时建在这两个地块上,没有任何问题。
具体而言,高桥按照以下程序存储商品:
- 选择一组 S 建造仓库的地块(S 可能为空)。没有两块地 S 可以通过走廊直接连接。
- 对于每批 i in S,在之间分配整数数量的货物 0 和 P_i 包括在内。很多不在 S 没有仓库,所以他们的货物数量是 0.
- 所有批次的货物总数不得超过 M.
找出所有批次中货物总金额的最大可能值。
约束
- 1 \leq N \leq 40
- 1 \leq M \leq 10^{15}
- 0 \leq K \leq \frac{N(N-1)}{2}
- 1 \leq P_i \leq 10^{12} (1 \leq i \leq N)
- 1 \leq U_i < V_i \leq N (1 \leq i \leq K)
- (U_i, V_i) \neq (U_j, V_j) (i \neq j)
- 所有输入值均为整数
输入
N M K P_1 P_2 \ldots P_N U_1 V_1 U_2 V_2 \vdots U_K V_K
- 第一行包含整数 N 代表手数,整数 M 表示存储上限,整数 K 代表走廊的数量,以空格分隔。
- 第二行包含整数 P_1, P_2, \ldots, P_N 代表每批最大存储容量,以空格分隔。
- 来自 3rd 行到 (K + 2)第线,给出走廊信息。
- 的 (2 + i)第行表示 i第走廊直接连接地块 U_i 和很多 V_i.
输出
输出高桥可以存储的最大货物总量,作为一行中的单个整数。
示例输入 1
4 10 2 3 5 4 6 1 2 3 4
示例输出 1
10
示例输入 2
6 100 5 10 20 30 15 25 5 1 2 2 3 3 4 4 5 5 6
示例输出 2
65
示例输入 3
10 1500000000000 8 100000000000 200000000000 150000000000 300000000000 250000000000 50000000000 400000000000 180000000000 350000000000 120000000000 1 2 2 3 1 5 4 7 4 9 5 6 7 9 8 9
示例输出 3
1150000000000