← 返回题目列表

AtCoder · awc0038_e

E. 仓库安置计划

中文机器翻译题面 查看原题

分数: 433 分

问题陈述

高桥是一个工业园的经理,该工业园包括 N 很多。每批编号从 1 to N,以及一个能够存储多达 P_i 大量货物可建造成吨 i.

有一天,请求存储总共 M 工业园区吨货。高桥希望在满足下述条件的同时存储尽可能多的货物。

工业园有 K 走廊, i第走廊直接连接地块 U_i 和很多 V_i。在由走廊直接连接的两个地块上同时建造仓库是 禁止,因为送货卡车的路线会互相干扰。如果两个地块没有通过走廊直接连接,那么仓库可以同时建在这两个地块上,没有任何问题。

具体而言,高桥按照以下程序存储商品:

  1. 选择一组 S 建造仓库的地块(S 可能为空)。没有两块地 S 可以通过走廊直接连接。
  2. 对于每批 i in S,在之间分配整数数量的货物 0 和 P_i 包括在内。很多不在 S 没有仓库,所以他们的货物数量是 0.
  3. 所有批次的货物总数不得超过 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